python - 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

它是 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 开始，gcd is in the math module ; fractions 中的那个已被弃用。此外，inspect.getsource 不再返回任何一种方法的解释性源代码。