http://blog.csdn.net/jtujtujtu/article/details/4407171
2009
参考：http://zhidao.baidu.com/question/50322580.html
辗转相除法求最大公约数：
辗转相除法, 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至前300年。它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。
证明：
设两数为a、b(b＜a)，求它们最大公约数gcd(a、b)的步骤如下：用b除a，得a＝bq1＋r1（0≤r1＜b）。若r1=0，则gcd(a，b)＝b；若r1≠0，则再用r1除b，得b＝r1q2＋r2（0≤r2＜r1）。若r2＝0，则gcd(a，b)＝r1，若r2≠0，则继续用r2除r1，……如此下去，直到能整除为止。其最后一个非零余数即为gcd(a，b)。
算法:
辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：
1. 若 r 是 a ÷ b 的余数, 则
gcd(a,b) = gcd(b,r)
2. a 和其倍数之最大公因子为 a。
另一种写法是：
1. a ÷ b，令r为所得余数（0≤r＜b）
若 r = 0，算法结束；b 即为答案。
2. 互换：置 a←b，b←r，并返回第一步。
c/c++ 代码：
递归法：
[c-sharp]
int gcd(int a, int b) //(a>b)
{
if(a==0 || b==0)
return 0;
int t=a%b;
if(t==0)
return b;
return gcd(b, t);
}
循环法：
[c-sharp]
int gcd(int a, int b) //a>b
{
if(a==0 || b==0)
return 0;
while(b!=0)
{
int t=a%b;
a=b;
b=t;
}
return a;
}
另：考虑大数时，需要分析可行性，由此得到一些简化方法，譬如：
若x, y均为偶数，f（x, y）= 2 * f（x/2, y/2）= 2 * f（x>>1, y>>1）
若x为偶数，y为奇数，f（x, y）= f（x/2, y）= f（x>>1, y）
若x为奇数，y为偶数，f（x, y）= f（x, y/2）= f（x, y>>1）
若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（11112, 1102）
= 2 * f（11112, 112）
= 2 * f（11002, 112）
= 2 * f（112, 112）
= 2 * f（02, 112）
= 2 * 112
= 6
根据上面的规律，具体代码实现如下：
代码清单2-16
BigInt gcd(BigInt x, BigInt y)
{
if(x
return gcd(y, x);
if(y == 0)
return x;
else
{
if(IsEven(x))
{
if(IsEven(y))
return (gcd(x >> 1, y >> 1)
else
return gcd(x >> 1, y);
}
else
{
if(IsEven(y))
return gcd(x, y >> 1);
else
return gcd(y, x - y);
}
}
}
有了最大公约数，最小公倍数则很简单了，a*b/gcd(a,b).
如有任何看法，欢迎交流：）
mosesyuan at gmail.com