给定两个数，例如

a

=

27

,

b

=

12

a=27, b=12

a=27,b=12，我们知道a, b的最大公因数为3。 下面将介绍两种求最大公因数的高效方法：

（1）辗转相除法

辗转相除法有一个高大上的名字：欧几里得法。 下面模拟辗转相除法求a, b的最大公因数：

辗转相除法的代码如下：这里采用递归，并且是精简形式。

int gcd_1(int a, int b){

return b == 0 ? a:gcd_1(b, a%b);

}

（2）辗转相减法

辗转相减法也有一个高大上的名字：尼考曼彻斯法。 下面模拟辗转相减法求a, b的最大公因数：

辗转相减法的代码如下：这里也采用递归，并且也是精简形式。

int gcd_2(int a, int b){

return a == b ? a:gcd_2(a>b ? a-b:a, b>a ? b-a:b);

}