方法1 )辗转相除(温柔老师算法) mgdmy算法也称为辗转相除，用于计算两个整数a、b的最大公约数。 其计算原理取决于http://www.Sina.com/:gcd(a，b )=gcd(b ) b，a mod b )
定理:a可以表示为a=kb r，r=a mod b
如果设d是a、b的公约数，则得到如下
d|a，d|b，而且r=a - kb，所以d|r
因此，d是(b，a mod b )的公约数
假设d是(b，a mod b )的公约数
d | b，d |r，其中a=kb r
因此，d也是(a，b )的公约数
因此，[a，b]和[b，a mod b的公约数相同，其最大公约数也必然相等，被证明
代码如下所示。 intgcd(inta，int b ) if ) b==0)返回a； returngcd(b，a%b )； (}int main ) ) { int a=12，b=18； intRES=gcd(a，b )； cout a '和' b '的最大公约数为' resendl； 返回0； (方法2 )更相减损法：更相减损术来源于中国古代的《九章算术》，也是一种求解最大公约数的算法。
首先判断两个数的大小，如果两个数相等，其数量本身就是其最大公约数。
不相等时，从大的数中减去小的数，与用该小的数减去它们的结果进行比较。 如果相等，则该差为它们的最大公约数。 不相等时，继续的操作。
代码如下所示。 intgcd(inta，int b ) while(true ) /减去小数位数以保存结果(if(ab ) a-=b； }elseif(ab ) { b -=a； (} else//如果两个数相等，则该数为最大公约数) { return a； } }}int main () { int a=12，b=18； intRES=gcd(a，b )； cout a '和' b '的最大公约数为' resendl； 返回0； )方法3 )3:Stein算法(将换相除法和更相减损法的优越性与移位运算相结合)移位运算的性能非常快，这一点我们已经知道。 对于给定的正整数a和b，可以得到以下结论。 在此，gcb(a，b )意味着求出a，b的最大公约数的函数
在a和b都为偶数的情况下，gcb(a，b )=2gCB ) a/2，b/2 )=2gCB ) a1，b1 ) a为偶数，b为奇数的情况下，gcb ) a，b )=gcb ) a/2，b )=gcb ) 代码如下所示。 intgcd(inta，int b ) if ) a==0)返回b； if(b==0)返回a； if(a%2==0b%2==0) return2*gcd ) a1，b 1 )； ELSEif(a%2==0) returngcd ) a1，b )； ELSEif(B%2==0)返回gcd (a ) a，b 1 )； ELSEreturngcd(ABS(a-b )，min ) a，b )； (}int main ) ) { int a=12，b=18； intRES=gcd(a，b )； cout a '和' b '的最大公约数为' resendl； 返回0； }