33558 blog.csdn.net/jtujtujtu/article/details/4407171
2009
辗转相除求出最大公约数：
辗转相除，又名体贴包算法(Euclidean algorithm )是求解两个正整数最大因子的算法。 这是已知的最古老的算法，可以追溯到前300年。 它首次出现在关怀包的《几何原本》 (第VII卷，命题I和ii )，但在中国可以追溯到出现在东汉的《九章算术》。 不需要将二数作为质因子进行分解。
证明：
将两数设为a、b(b<； 设a )，求出它们的最大公约数gcd ) a，b )的步骤是将a除以b，求出a=BQ1 R1(0R1<； 得到b )。 当r1=0时，gcd(a，b )=b； 当r10时，再用r1除b，得到B=R1Q2 R2(0R2<； 得到R1)。 如果r2=0，GCD(A，b )=r1，r20，则继续用r2除r1，……直到能被整除为止。 其最后的非零馀数为gcd(a，b )。
算法：
辗转相除利用以下性质决定两个正整数a和b的最大公因子。
1 .如果r是a b的余数
GCD(a，b )=gcd (b，r ) )。
2. a及其倍数的最大公因子是a。
另一种写法是：
1 .设ab，r为得到的馀数(0r ) b )
在r=0的情况下，算法结束； B是答案。
2 .调换：放置ab、br，返回第一步。
c/c代码：
递归法：
intgcd(inta，intb )/(ab ) ) ) ) )。
{
if(a==0||b==0)
返回0；
intt=a%b；
if(t==0) )。
返回；
returngcd(b，t )；
}
循环法：
intgcd(inta，intb )//ab
{
if(a==0||b==0)
返回0；
while(b！=0)
{
intt=a%b；
a=b；
b=t；
}
returna；
}
另外，在考虑数字时，需要分析可行性，从而得到几种简化方法。 例如，以下内容：
如果x、y都是偶数，则f(x，y )=2* f (x/2，y/2 )=2* f (x1，y1 ) ) ) ) ) ) ) ) )。)
x为偶数，y为奇数时，f(x，y )=f ) x/2，y )=f ) x1，y ) ) ) ) ) ) ) ) ) 652 )
如果x是奇数，y是偶数，则f(x，y )=f ) x，y/2 )=f ) x，y1 ) ) ) ) ) ) ) ) ) ) ) ) )。
如果x、y都是奇数，则f(x，y )=f ) x、x -y )，
那么，f(x，y )=f ) x，x -y )之后，) x -y )是偶数，下一步一定有除以2的操作。
因此，最坏情况下的时间复杂度为o(log2 ) max (x，y ) )。
考虑以下情况。
f (42，30 )=f ) 1010102，111102 ) )。
=2* f (101012，11112 ) )。
=2* f (1112，1102 ) ) )
=2* f (1112，112 ) ) ) ) ) ) ) ) ) ) ) ) ) )0) 0
=2* f (11002，112 ) )。
=2* f (112，112 ) ) )。
=2* f (02，112 ) ) )
=2 * 112
=6
根据上面的规律，具体的代码实现如下。
代码清单2-16
bigintgcd(bigintx，BigInt y ) )。
{
if(xy ) )。
returngcd(y，x )；
if(y==0) )。
返回x；
else
{
if(isEven ) x ) )
{
if(isEven ) y ) )
return(gcd ) x1，y 1；
else
returngcd(x1，y )；
}
else
{
if(isEven ) y ) )
returngcd(x，y 1 )；
else
returngcd(y，x - y )；
}
}
}
如果有最大公约数，最小公倍数很简单。 a*b/gcd(a，b )。
如果您有意见，欢迎交流：)
mosesyuan at gmail.com