工学1号馆

home

最大公约数算法

By Wu Yudong on July 21, 2016

最大公约数指两个或多个整数共有约数中最大的一个。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)。算法的步骤如下:

第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。
第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
也可以省去判断偶数的步骤,直接使用减法一直进行下去
例:用更相减损术求98与63的最大公约数。
这个过程可以简单的写为:
(98,63)=(35,63)=(35,28)=(7,28)=(7,21)=(7,14)=(7,7)=7.
算法实现代码如下:
int gcd(int x, int y)
{
	if (x < y)
		return gcd(y, x);
	if (!y)
		return x;
	else
		return gcd(x - y, y);
}
比较辗转相除法与更相减损术的区别
(1)都是求最大公因数的方法,计算上辗转相除法以除法为主,更相减损术以减法为主,计算次数上辗转相除法计算次数相对较少,特别当两个数字大小区别较大时计算次数的区别较明显。
(2)从结果体现形式来看,辗转相除法体现结果是以相除余数为0则得到,而更相减损术则以减数与差相等而得到。

改进算法

辗转相除法的问题在于计算复杂的大整数除法运算,更相减损法虽然改为减法运算,一定程度上降低了计算的复杂度,但是减法的迭代次数太多。改进的算法基于以下两点:

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

No comments yet.
To verify that you are human, please fill in "七"(required)