本文的讨论都在整数范围内。
假设有两个正整数：20和30。 $20 = 1 \times 20$，所以1和20是20的约数，$20 = 2 \times 10$，所以2和10是20的约数，等等。
求解20和30的最大公因数
本文一开始的例子即是列举法
20 = 2 * 10 = 2 * 2 * 5
30 = 2 * 15 = 2 * 3 * 5
所以 gcd(20, 30) = 2 * 5 = 10
2 | 20 30
-------
5 | 10 15
-------
2 3
所以 gcd(20, 30) = 2 * 5 = 10
本小节从辗转相减推导辗转相除，丝滑自然。辗转相除的证明可以参本站的另一篇文章，它也给了相应的Java实现，和本文类似。
假若x和y的最大公约数是a，且它们可表示为
x = a * b
y = a * c
令两者之差 z = x - y
则 z = a * (b - c)
这说明两数的最大公约数是两数之差的因数。显然，a 也是 x, y, z 三数的公因数。如此，我们可以选用 x, y 中较小的数和 z 相减，继续相减，直到能很明显看出两数的最大公约数是多少。
计算两个非负整数p和q的最大公约数：若q时0，则最大公约数为p。否则，将p除以q得余数r，p和q的最大公约数即为q和r的最大公约数。
例如：
gcd(48, 18) = gcd(48-18, 18)
= gcd(30, 18)
= gcd(30-18, 18)
= gcd(12, 18)
= gcd(12, 18-12)
= gcd(12, 6)
= gcd(12-6, 6)
= gcd(6, 6) // 到这里即可以看出最大公约数是6
= gcd(6 - 6, 6) // 本步是为了和使用出发的方式一致而作的冗余步骤
= gcd(0, 6)
=6
上面这个过程，可以简化为大数除以小数，再求小数和余数的最大公约数，如此反复，过程如下：
gcd(48, 18) = gcd(48 mod 18, 18)
= gcd(12, 18)
= gcd(12, 18 mod 12)
= gcd(12, 6)
= gcd(12 mod 6, 6)
= gcd(0, 6)
= 6
这里也可以不用考虑两个数大小的问题，每一步都是左数除以右数得余数，然后扔掉左数，将右数变为左数，余数变为右数即可。计算机实现按此方法代码最少。
如：
gcd(18, 48) = gcd(48, 18 mod 48)
= gcd(48, 18) // 可见，这一步相当于交换了左右数
= gcd(18, 48 mod 18)
= gcd(18, 12)
= gcd(12, 18 mod 12)
= gcd(12, 6)
= gcd(6, 12 mod 6)
= gcd(6, 0)
= 6
以上算法的终止条件是两数相等，或其中一数为0。
这个方法容易通过编程实现，特别是改进后使用除法求余的方式是程序解答的通行方法。
这里的两个示例来源于Createst Common Divisor (Wikipedia)
输入：两个正整数
输出：两数的最大公约数
public static long calculateGcd(long a, long b) {
if (a < 0 || b < 0) {
System.out.println("Only accept numbers greater than 0.");
}
if ( a == b) {
return a;
}
if (a == 0) {
return b;
}
if (b == 0) {
return a;
}
// if a is smaller than b, switch them.
if (a < b) {
long t = a;
a = b;
b = t;
}
long r = a % b;
return calculateGcd(b, r);
}
以上的代码是可以运行的，但其实我们依据4.1.4的末尾提到的解法
可简化改进为：
public static long calculateGcd(long a, long b) {
if (a < 0 || b < 0) {
System.out.println("Only accept numbers greater than 0.");
}
if (b == 0) {
return a;
}
long r = a % b;
return calculateGcd(b, r);
}
完整的代码实现参GreatestCommonDivisor.java，运行记录
$ javac GreatestCommonDivisor.java
$ java GreatestCommonDivisor
gcd(18, 48) = 6
long calculateGcd(long a, long b)
{
if (a < 0 || b < 0)
{
printf("Only accept numbers greater than 0.");
exit(0);
}
if (b == 0)
{
return a;
}
long r = a % b;
return calculateGcd(b, r);
}
完整的代码实现参gcd.c，其中包含了一个非递归版本，但可读性不佳，运行记录
$ gcc gcd.c -o gcd
$ ./gcd.exe
gcd(18, 48) = 6
gcd(18, 48) = 6
(Windows平台编译出的可执行文件，带有后缀名.exe，但在Linux上是没有后缀名的。)
TODO
TODO
TODO
TODO
TODO
TODO
TODO
TODO
后记，因为阅读《算法·第4版》(Robert & Kevin)，书中第一章第一页提到最大公约数算法，故做了一点小小的研究，记录于此。
【参考】