P207: Determine the greatest common divisor of two positive integer numbers

求最大公约数。

最大公因数

最大公因数（英语：highest common factor，hcf）也称最大公约数（英语：greatest common divisor，gcd）是数学词𢑥，指能够整除多个整数的最大正整数。而多个整数不能都为零。例如8和12的最大公因数为4。 整数序列$a$的最大公因数可以记为$(a_1,a_2,...,a_n)$或$gcd(a_1,a_2,...,a_n)$。 求两个整数最大公因数主要的方法：

• 穷举法：分别列出两整数的所有因数，并找出最大公因数。
• 质因数分解：分别列出两数的质因数分解式，并计算共同项的乘积。
• 短除法：两数除以其共同质因数，直到两数互质时，所有除数的乘积即为最大公因数。
• 辗转相除法：两数相除，取余数重复进行相除，直到余数为0时，直到余数为0时，前一个除数即为最大公因数。^wiki-hcf

照例先写测试用例：

「辗转相除法」是一个简单有效的求最大公约数的方法。

辗转相除法

在数学中，辗转相除法，又称欧几里得算法（英语：Euclidean algorithm），是求最大公因数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。^{wiki-division}

计算过程

辗转相除法是一种递回算法，每一步计算的输出值就是下一步计算时的输入值。设k表示步骤数（从0开始计数），算法的计算过程如下。

每一步的输入是都是前两次计算的非负余数$r_{k−1}$和$r_{k−2}$。因为每一步计算出的余数都在不断减小，所以，$r_{k−1}$小于$r_{k−2}$。在第k步中，算法计算出满足以下等式的商$q_k$和余数$r_k$：

$$r_{k-2} = q_kr_{k-1} + r_k$$

其中$0 ≤ r_k < r_{k−1}$。也就是$r_{k−2}$要不断减去$r_{k−1}$直到比$r_{k−1}$小。

为求简明，以下只说明如何求两个非负整数a和b的最大公约数（负数的情况是简单的）。在第一步计算时（k = 0），设$r_{−2}$和$r_{−1}$分别等于a和b，第2步（此时k = 1）时计算$r_{−1}$（即b）和$r_0$（第一步计算产生的余数）相除产生的商和余数，以此类推。整个算法可以用如下等式表示：

$$\begin{align*} a &= q_0b+r_0 \\ b &= q_1r_0+r_1 \\ r_0 &= q_2r_1+r_2 \\ r_1 &= q_3r_2+r_3 \\ ... \end{align*}$$

如果有$a < b$，算法的第一步实际上会把两个数字交换，因为这时a除以b所得的商$q_0$会等于0，余数$r_0$则等于a。然后，算法的第二步便是把b除以a，再计算所得之商和余数。所以，对于$k \geq 0$总有$r_k<r_{k−1}$，即运算的每一步中得出的余数一定小于上一步计算的余数。 由于每一步的余数都在减小并且不为负数，必然存在第N步时$r_N$等于0，使算法终止，$r_{N−1}$就是a和b的最大公因数。其中N不可能无穷大，因为在$r_0$和0之间只有有限个自然数。^{wiki-division}

完整的代码实现：

辗转相除法（euclid(a,b)）是一个递归算法。其接受两个整数a和b，且a>b（所以需要在外层按大小排列好两个整数），求出余数r0和r1，r0 = a % b, r1 = b % r0。

• 若r0为0则b为最大公约数；
• 若r1为0则r0为最大公约数；
• 若r0和r1皆不为0则r0, r1的最大公约数即是a, b的最大公约数，问题被简化为求r0, r1的最大公约数。

举个例子，输入整数36和63，求最大公约数：

1. 63大于36，以63为a以36为b，求得r0为27，r1为9。r0和r1皆不为0，所以求27和9的最大公约数。
2. 27为a，9为b，求得r0为0则b 9为最大公约数。

$$\begin{align*} 63 \mod 36 &= 27 \\ 36 \mod 27 &= 9 \\ 27 \mod 9 &= 0 \end{align*}$$

参考文献

^wiki-hcf. https://zh.wikipedia.org/wiki/最大公因数 ↩

^{wiki-division}. https://zh.wikipedia.org/wiki/辗转相除法 ↩