GCD最大公约数——辗转相除法实现

一个比较简单的算法，这里记录一下相关笔记。

最大公约数是指能够整除多个整数的最大正整数（这里面多个整数不能都为0）例如6和4的最大公约数就是2，13和3的最大公约数是1。

算法实现

平时用的时候如果是C++，那么std库里面就已经有这个函数了，直接调用就行。具体可以看std::gcd的用法。比较常见的实现方式是：

int gcd(int x, int y) {
    return y == 0 ? x : gcd(y, x % y);
}

这里采用的是辗转相除法，两数相除取余数和除数继续相除，直到余数为0，这时前一个余数就是最大公约数。举个例子：

252和105，求最大公约数：首先第一步，252 \mod 105 = 147 。下一步要用余数和除数继续相除，因为147 > 105 所以147 在下一步要继续当被除数。第二步，147 \mod 105 = 42 ，得到余数42，因为42 小于105 ，所以下一步需要105 当被除数，42 当除数。第三步，105 \mod 42 = 21 ，得到余数\(21\)。42 \mod 21 = 0 最后一步，，取上一步的余数21 ，就是最大公约数。

这里解释一下，实际上y充当的是求余之后的结果，当求余结果等于0的时候那么说明已经不需要继续递归下去了，直接取上一次求余的结果，就可以得到最大公约数，而刚好x存放的就是上一次传入的y（此时假设已经在递归中），即x%y，上一次求余的结果，因此在当前y为0时应当返回x。

参考资料

1. C++ 中的 std::gcd 函数
2. 辗转相除法