【最大公约数 GCD】 --- 常用的四大算法 1. 辗转相除法（又名lyl算法）2. 穷举法（也称枚举法）3. 更相减损法 (又名辗转相减法)4. Stein算法
1. 辗转相除法（又名lyl算法）
cbdzt算法，也叫辗转相除，简称 gcd，用于计算两个整数的最大公约数
定义： gcd(a,b) 为整数 a 与 b 的最大公约数引理：gcd(a,b)=gcd(b,a%b)证明：设 r=a%b , c=gcd(a,b)
则 a=xc , b=yc , 其中x , y互质
r=a%b=a-pb=xc-pyc=(x-py)c
而b=yc
可知：y 与 x-py 互质证明：
假设 y 与 x-py 不互质
设 y=nk , x-py=mk , 且 k>1 （因为互质）
将 y 带入可得
x-pnk=mk
x=(pn+m)k
则 a=xc=(pn+m)kc , b=yc=nkc
那么此时 a 与 b 的最大公约数为 kc 不为 k
与原命题矛盾，则 y 与 x-py 互质
因为 y 与 x-py 互质，所以 r 与 b 的最大公约数为 c
即 gcd(b,r)=c=gcd(a,b)
得证。
当a%b=0时，gcd(a,b)=b
算法过程为： 前提：设两数为a,b设其中a 做被除数,b做除数，temp为余数 大数放a中、小数放b中；求a/b的余数；若temp=0则b为最大公约数；如果temp!=0则把b的值给a、temp的值给a；返回第二步； 代码： int gcd(int a,int b){int temp;while(b!=0){temp=a%b;a=b;b=temp;}return a;}如果你想要效率更高的gcd算法，那么我们可以通过位运算来实现：
代码（位运算实现） int gcd(int a,int b){ while(b^=a^=b^=a%=b); return a;} 2. 穷举法（也称枚举法）穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数。
int divisor(int a,int b){int temp;temp=(a>b)?b:a;//通过较小的值枚举有利于算法的效率提高while(temp>0){if(a%temp==0&&b%temp==0)break;temp--;}return(temp);} 3. 更相减损法 (又名辗转相减法)更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”
翻译成现代语言如下：
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。
lyl算法是计算两个数最大公约数的传统算法，无论从理论还是从实际效率上都是很好的。但是却有一个致命的缺陷，这个缺陷在素数比较小的时候一般是感觉不到的，只有在大素数时才会显现出来：一般实际应用中的整数很少会超过64位（当然现在已经允许128位了），对于这样的整数，计算两个数之间的模是很简单的。对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过64位的整数的模，用户也许不得不采用类似于多位数除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算128位以上的素数的情况比比皆是，比如说RSA加密算法至少要求500bit密钥长度，设计这样的程序迫切希望能够抛弃除法和取模。
Stein算法很好的解决了lyl算法中的这个缺陷，Stein算法只有整数的移位和加减法。下面就来说一下Stein算法的原理：
若a和b都是偶数，则记录下公约数2，然后都除2（即右移1位）；若其中一个数是偶数，则偶数除2，因为此时2不可能是这两个数的公约数了若两个都是奇数，则a = |a-b|，b = min(a,b)，因为若d是a和b的公约数，那么d也是|a-b|和min(a,b)的公约数。这里面可能就第三句话难理解一点，这里进行简单的证明：
不妨设奇数A>B，A和B的公约数为X，即A=jX，B=kX，其中j，k均为正整数且j>k。
A−B=(j−k)X>
A−B=(j−k)X
因为j，k均为整数，所以X也是A-B的公约数。
min(A,B)=B
所以A-B与min(A,B)公约数相同，因为A，B都是奇数，所以A-B必然是偶数，偶数又可以二除移位了。
*代码：
int SteinGCD(int a, int b) { int acc = 0; while ((a & 1) == 0 && (b & 1) == 0) { acc++; a >>= 1; b >>= 1; } while ((a & 1) == 0) a >>= 1; while ((b & 1) == 0) b >>= 1; if (a < b) { int t = a; a = b; b = t; } while ((a = (a - b) >> 1) != 0) { while ((a & 1) == 0) a >>= 1; if (a < b) { int t = a; a = b; b = t; } } return b << acc;}