C++ 最大公约数 Greatest Common Divisor GCD

数据结构、算法与应用 第一张练习 23

当两个非负整数x和y都是0的时候，他们的最大公约数是0. 当两者至少有一个不是0的时候，他们的最大公约数是可以除尽二者的最大整数。 因此gcd(0,0)=0, gcd(10,0)=gcd(0,10)=10,而gcd(20,30)=10.

求最大公约数的欧几里得算法（Euclid's Algorithm）是一个递归算法：

    x                       (y=0)
    gcd(y,x mode y)         (y>0)

其中mod是模数运算子（modulo operator），相当于C++取余操作符%.

以下为算法

递归版：

int GCD( int x, int y ){

    if( y==0 ){
        return x;
    }
    return GCD( y, x%y );
}