python - Python 中最大公约数的代码

关闭。这个问题需要更多 focused 。它目前不接受答案。












想改善这个问题吗？更新问题，使其仅关注 editing this post 的一个问题。

2年前关闭。



Improve this question




a 和 b 的最大公约数 (GCD) 是将两者相除且无余数的最大数。

找到两个数的 GCD 的一种方法是欧几里德算法，该算法基于以下观察:如果 r 是 a 除以 b 的余数，那么 0x21341 则为 0x2134作为基本情况，我们可以使用 gcd(a, b) = gcd(b, r) 。

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

最佳答案

它是 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 不再返回任何一种方法的解释性源代码。

关于python - Python 中最大公约数的代码，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11175131/