【编程之美】 2.7最大公因数

辗转相除

1
2
3

int gcd(int a, int b) {
    return (b == 0) ? a : gcd(b, a%b);
}

另一种方法
需要实现大整数类，其中大整数可以用string或者数组保存。

int gcd2(BigInt a, BigInt b) {
    if (a < b) { return gcd2(b, a); }
    if (b == 0) { return  a; }
    else {    return gcd2(a - b, b);    }
}