Python中最大公约数的代码

Question

a和b的最大公约数（GCD）是将二者相除而不留余数的最大数。

找到两个数的GCD的一种方法是Euclid算法，它基于这样的观察：如果r是a除以b时的余数，那么gcd(a, b) = gcd(b, r)。作为基本情况，我们可以使用gcd(a, 0) = a。

编写一个名为gcd的函数，它接受参数a和b，并返回它们的最大公约数。

Answer 1

使用m-n的算法可以运行非常长的时间。

这个表现更好：

def gcd(x, y):
    while y != 0:
        (x, y) = (y, x % y)
    return x

Answer 2

这个版本的代码使用Euclid算法来查找GCD。

def gcd_recursive(a, b):
    if b == 0:
        return a
    else:
        return gcd_recursive(b, a % b)

Answer 3

是in the standard library。

>>> from fractions import gcd
>>> gcd(20,8)
4

Python 2.7中inspect模块的源代码：

>>> print inspect.getsource(gcd)
def gcd(a, b):
    """Calculate the Greatest Common Divisor of a and b.

    Unless b==0, the result will have the same sign as b (so that when
    b is divided by it, the result comes out positive).
    """
    while b:
        a, b = b, a%b
    return a

从Python 3.5开始，gcdis in the ^{} module；不推荐使用fractions中的一个。此外，inspect.getsource不再返回任何方法的解释性源代码。