最大公约数 —— 小灰的算法之旅读书笔记
辗转相除法(欧几里得算法)
两个正整数a和b(a>b),他们的最大公约数等于a除以b的余数c和b之间的最大公约数
更相减损术
两个整数a和b(a>b),它们的最大公约数等于a-b的差值c和b的最大公约数
更相减损术和移位结合
-
a和b都为偶数的时候,a和b的最大公约数为2*(a/2和b/2的最大公约数)
-
a和b为一奇一偶的时候,将偶数除以2,求两个奇数的最大公约数
-
a和b为奇数的时候,使用更相减损术运算一次,继续求最大公约数
代码实现
public class GreatestCommonDivisor {
public int gcd(int a, int b) {
//如果a==b,即为a和b的最大公约数
if (a == b) {
return a;
}
//如果a和b都是偶数
if ((a&1) == 0 && (b&1) == 0) {
return gcd(a>>1, b>>1)<<1;
} else if ((a&1) == 0 && (b&1) != 0) { //a是偶数,b是奇数
return gcd(a>>1, b);
} else if ((a&1) != 0 && (b&1) == 0) { //a是奇数,b是偶数
return gcd(a, b>>1);
} else { //a和b都是奇数,使用更相减损术
int big = a > b ? a : b;
int small = a > b ? b : a;
return gcd(big - small, small);
}
}
public static void main(String[] args) {
GreatestCommonDivisor greatestCommonDivisor = new GreatestCommonDivisor();
System.out.println(greatestCommonDivisor.gcd(25, 5));
System.out.println(greatestCommonDivisor.gcd(100, 80));
System.out.println(greatestCommonDivisor.gcd(27, 14));
}
}