最近看programming pearls 第二章 源码中有
求最大公约数的代码。。看不太懂
于是查到原理如下：（顺便简单叙述下两种求最大公约数的方法）
（ps:以下大部分内容来自互联网，会有少量个人注解）
一、更相减损法
更相减损术,又称"等值算法"
关于约分问题,实质是如何求分子,分母最大公约数的问题。《九章算术》中介绍了这个方法,叫做”更相减损术”,数学家刘徽对此法进行了明确的注解和说明,是一个实用的数学方法。
例：今有九十一分之四十九,问约之得几何?
我们用(91,49)表示91和49的最大公约数.按刘徽所说,分别列出分子,分母。
“以少减多,更相减损,求其等也,以等数约之,等数约之,即除也,其所以相减者皆等数之重叠,故以等数约之。”
译文如下：
约分的法则是：若分子、分母均为偶数时，可先被2除，否则，将分子与分母之数列在它处，然后以小数减大数，辗转相减，求它们的最大公约数，用最大公约数去约简分子与分母。
其与古希腊欧几里德所著的《几何原本》中卷七第一个命题所论的相同。列式如下:
91 49
42 49
42 7
35 7
28 7
21 7
14 7
7 7
这里得到的7就叫做“等数”,91和49都是这等数的重叠(即倍数),故7为其公约数.而7和7的最大公约数就是7,(7,7)=7,所以(91,49)=(42,7)=(7,7)=7
更相减损术在现代仍有理论意义和实用价值.吴文俊教授说:“在我国,求两数最大公约数即等数,用更相减损之术,将两数以小减大累减以得之,如求24与15的等数,其逐步减损如下表所示:(24,15)->(9,15)->(9,6)->(3,6)->(3,3)
每次所得两数与前两数有相同的等数,两数之值逐步减少,因而到有限步后必然获得相同的两数,也即所求的等数,其理由不证自明。
这个寓理于算不证自明的方法,是完全构造性与机械化的尽可以据此编成程序上机实施”.吴先生的话不仅说明了此法的理论价值,而且指明学习和研究的方向.
代码实现如下：
int gcd(int a,int b)
{
while(a!=b)
{
if(a>b)
a-=b;
else
b-=a;
}
return a;
}
二、辗转相除法
自然语言描述
辗转相除法是利用以下性质来确定两个正整数 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，并返回第一步。
原理及其详细证明
设两数为a、b(b<a），用gcd(a,b）表示a，b的最大公约数，r=a mod b 为a除以b以后的余数，辗转相除法即是要证明gcd(a,b)=gcd(b,r）。
第一步：令c=gcd(a,b），则设a=mc，b=nc
第二步：根据前提可知r =a-kb=mc-knc=(m-kn)c
第三步：根据第二步结果可知c也是r的因数
第四步：可以断定m-kn与n互素【否则，可设m-kn=xd，n=yd，（d>1），则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公约数成为cd，而非c】
从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r）。
证毕。
代码实现如下
//递归
int gcd(int a,int b)
{
if(b==0)
return a;
else
return gcd(b,a%b);
}
//循环
int gcd(int a,int b)
{
int r;
while(b!=0)
{
r=a%b;
a=b;
b=r;
}
return a;
}
对于求最大公约数都没有仔细研究过。。。鄙视自己。。
更相减损法（等值法）更是都没有听说过。。。严重怀疑自己知识面。。。。
个人觉得等值法效率更高，只存在加减。。