最大公约数

约数？最大公约数？ 如果整数a能被整数b整除，那么a叫做b的倍数，b叫做a的约数。

给定两个整数a、b，两个数的所有公共约数中最大值即为最大公约数(Greatest Common Divisor,GCD)。例如12和16的最大公约数是4。

如何计算两个数的最大公约数？

• 欧几里得：辗转相除法(欧几里得算法)，公式：gcd(a,b) = gcd(b, a mod b)
  • 例：gcd(60, 21) = gcd(21, 18) = gcd(18, 3) = gcd(3, 0) = 3

-《九章算术》：更相减损术

欧几里得算法

根据上面的算法公式，代码实现：

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


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


print(gcd(12, 16))  # 4
print(gcd_r(12, 16))  # 4

分数实现

我们通过欧几里得算法，来实现一个分数计算。