最大公约数指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。
求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数，a，b的最小公倍数记为[a，b]。
辗转相除法
求最大公约数的方法最著名的要属于辗转相除法，辗转相除法是求两个自然数的最大公约数的一种方法，也叫欧几里德算法。算法依赖于欧几里德定理：若 a=b×r+q ，则gcd(a, b) = gcd(b, q).
算法比较简单：
int gcd(int x, int y)
{
return (!y) ? x : gcd(y, x % y);
}
更相减损法
更相减损法是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。基于gcd(x, y) = gcd(x-y, y)。算法的步骤如下：
int gcd(int x, int y)
{
if (x < y)
return gcd(y, x);
if (!y)
return x;
else
return gcd(x - y, y);
}
改进算法
辗转相除法的问题在于计算复杂的大整数除法运算，更相减损法虽然改为减法运算，一定程度上降低了计算的复杂度，但是减法的迭代次数太多。改进的算法基于以下两点：
1、对于x与y，如果y=k*y1, x=k*x1，那么有gcd(y, x)=gcd(y1, x1)
2、如果x=p*x1，假设p为素数，并且y不能被p整除，那么gcd(x, y)=gcd(p*x1, y)=gcd(x1, y)
注意到2为素数，并且对于其他大数而言，可以使用移位运算来代替除以2，提高效率
取p=2，
若x，y均为偶数，gcd(x, y)=2*gcd(x/2, y/2)=2*gcd(x>>1, y>>1)
若x为偶数，y为奇数，gcd(x, y)=gcd(x/2, y)=gcd(x>>1, y)
若x为奇数，y为偶数，gcd(x, y)=gcd(x, y/2)=gcd(x, y>>1)
若x，y均为奇数，gcd(x, y) = gcd(y, x-y)，此时 x-y为一个偶数，转到前面的除以2操作
最坏的情况下算法的时间复杂度是O(log(max(x,y)))
算法实现如下：
//判断整数是否为奇数
//返回1表示奇数，返回值为0表示偶数
int isEven(int value)
{
return !((value & 1) == 0);
}
int gcd(int x, int y)
{
if (x < y)
return gcd(y, x);
if (!y)
return x;
else {
if (isEven(x)) {
if (isEven(y))
return (gcd(x >> 1, y >> 1) << 1);
else
return gcd(x >> 1, y);
} else {
if (isEven(y))
return gcd(x, y >> 1);
else
return gcd(y, x - y);
}
}
}
Comments