Python中最大公约数的代码

Question

a和b的最大公约数(GCD)是将两者分开而没有余数的最大数.

找到两个数字的GCD的一种方法是Euclid算法,该算法基于以下观察结果:if 是除以之后r的余数.作为基础案例,我们可以使用.abgcd(a, b) = gcd(b, r)gcd(a, 0) = a

写一个函数调用GCD是需要的参数a和b返回他们的最大公约数.

Answer 1

它在标准库中.

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

inspectPython 2.7中模块的源代码:

>>> 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 就在math模块中 ; 中的一个fractions被弃用了.此外,inspect.getsource不再返回任何一种方法的解释性源代码.

Answer 2

使用mn的算法运行得非常长.

这个表现得更好:

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

Answer 3

此版本的代码使用Euclid的算法来查找GCD.

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

Answer 4

gcd = lambda m,n: m if not n else gcd(n,m%n)

Answer 5

使用递归，

def gcd(a,b):
    return a if not b else gcd(b, a%b)

使用while ,

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

使用拉姆达，

gcd = lambda a,b : a if not b else gcd(b, a%b)

>>> gcd(10,20)
>>> 10