Python之美：最大公约数

在Lib/fractions.py中，Python为我们提供了计算两个整数最大公约数的函数。

fractions.gcd(a, b) Return the greatest common divisor of the integers a and b. If either a or b is nonzero, then the absolute value of gcd(a, b) is the largest integer that divides both a and b. gcd(a,b) has the same sign as b if b is nonzero; otherwise it takes the sign of a. gcd(0, 0) returns 0.

看看这段说明，这个函数的实现没个十行八行的代码肯定搞不定吧？我们再看看Python是如何实现这个函数的。

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

第一行是函数定义，最后一行是函数返回，真正的实现代码竟然只有2行，真是有些不可思议！看完这个函数的实现，也许你马上就联想到了小学时老师教给我们计算两个整数最大公约数的方法：辗转相除法。可你知道为什么辗转相除就能得到两个整数的最大公约数吗？

计算最大公约数（greatest common divisor，简称gcd）的算法最早记录在古希腊数学家欧几里得（Euclid）的几何原本（Elements）中，几何原本共有13卷，第7,8,9卷讲的都是数论的内容。可数论的内容为何写到几何书里了？大家不要忘了，数字是对生活中的长度、数量的抽象。在几何原本中，欧几里得对数字的分析是基于线段的长度来进行的。他把整数间的整除关系，表示为线段间的测尽关系。由于欧几里得早在公元前300年就发现了这一算法，所以该算法也叫做欧几里得算法（Euclidean algorithm）。那么我们就一起看看当年欧几里得是如何证明这一问题的。

定义 VII.1 一个单位是一切事物凭借它存在的基础，被称为一。 VII.2 一个数是由许多单位合成的。 VII.5 若一个较大数能被一个较小数测尽（整除），那么它是较小数的倍数。

命题 VII.2 给定两个正整数数，可以找到它们的最大公约数。

证明 设：AB和CD为给定的两个正整数，现在要求的是找到AB和CD的最大公约数。

如果CD测尽AB，因为它也自测尽，那么CD是CD和AB的公约数，同时它也是最大的，因为没有既大于CD又能测尽CD的数。

如果CD测不尽AB，设余量为AE，那么用AE去量CD，如果测不尽，设余量为CF，再用CF去量AE，直到后面的余量测尽前面的余量。

这样一直下去一定会出现测尽的情况，因为余数越来越小，当余数是一个单位时（VII.1），下一轮这一个单位肯定能测尽任何一个数（定义VII.2）。

假设最终我们找到了CF能够测尽AE，因为AE测尽DF，所以CF测尽DF。又因为CF自测尽，所以CF也测尽整个CD。

又因为CD测尽BE，所以CF也测尽BE，它同时也测尽AE，所以CF测尽整个AB。因为CF既测尽AB又测尽CD，所以CF是AB和CD的一个公约数。

我们还需要进一步证明它也是最大的。如果CF不是AB和CD的最大公约数，那么必然有一个更大的数能同时测尽AB和CD，我们设其为g。

因为g能测尽CD，CD能测尽BE，所以g能测尽BE。而g又能测尽整个AB，所以g能测尽AE。

因为AE能测尽DF，所以g能测尽DF。又因为g能测尽CD，所以g能测尽余量CF。即：较大的数g能测尽较小的数CF，这是不可能的。所以没有大于CF，又能测尽AB和CD的数。

因此，CF是AB和CD的最大公约数。

上面的算法总结一句话就是，不断用后面的余量去量前面的余量，直到测尽为止。

∎