欧几里得（辗转相除）算法

欧几里得算法是指计算两个数时
将较大的A除以较小的B
得到余数C
再用C除较小的数，反复循环，最后得到0，最后得到0时较小的数就是最大公约数。

代码

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    int c = a % b;
    return gcd(b, c);
}

问题

1.为什么无论为gcd()输入的参数哪一个大，最后都能求出公约数？

这是因为在计算最大公约数的过程中，我们不断使用较小的数去除以较大的数，得到余数后，将较大的数替换为余数，然后再将较小的数替换为原来的较大的数。这个过程不断重复，直到余数为零。

假设 a > b，我们第一次将 a 除以 b 得到余数 c1，那么 a 可以表示为 a = b * k1 + c1，其中 k1 是整数商。然后我们将 b 替换为 c1，c1 替换为 b，这时有 a = b * k1 + c1，继续将 b 除以 c1，得到余数 c2，然后将 c1 替换为 c2，b 替换为 c1，这时有 a = b * k2 + c2，其中 k2 是新的整数商。如此重复，直到余数为零，此时 b 即为最大公约数。

因此，无论 a 和 b 的大小关系如何，都不会影响最终的结果，最大公约数总是可以正确地计算出来。

2.为什么叫gcd?

GCD是Greatest Common Divisor的意思