[欧几里得算法] #Python #算法

gcd.py

def gcd(m, n):
    if n == 0:
        m, n = n, m
    while m != 0:
        m, n = n%m, m
    return n

"""
最著名的寻找最大公因数的方法是欧几里得算法.
欧几里得算法规定：
对于两个整数 m 和 n，如果 n 能整除 m，那么就将 n 除以 m 的结果作为新的 n，
如果 n 不能再整除 m，那么最大公因数就是 n 或者 m 被 n 整除的余数。
注意这个最大公因数的算法只适用于分母是正数的情况。
因为我们可以把负分数的负号归结于分子，所以这种算法还是比较实用的。
"""