最大公约数

给定两个正整数 ab,求他们的 最大公约数(Greatest Common Divisor,GCD)。

我们最常用的解法是 欧几里得算法(Euclidean Algorithm),又称 辗转相除法,其原理是 两个整数的最大公约数等于其中较小的数和两数相除的余数的最大公约数

用大数(假设为 a)除以小数(假设为 b)得到余数 d

  • d == 0,则 b 为最大公约数;
  • d != 0,则令 a = d,重复此步骤。

Python 3 实现如下:

1
2
3
4
5
6
7
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    remainder = a % b
    if remainder == 0:
        return b
    else:
        return gcd(b, remainder)

如果要求 多个数的最大公约数,就在外面简单包一层,设一个全局最大公约数,然后遍历就好了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def gcd(*nums):
    def gcd_helper(a, b):
        a, b = max(a, b), min(a, b)
        remainder = a % b
        if remainder == 0:
            return b
        else:
            return gcd_helper(b, remainder)
    ret = nums[0]
    for num in nums[1:]:
        ret = gcd_helper(ret, num)
    return ret

最后,其实 Python 的内置模块就有 gcd 的实现:from math import gcd

最小公倍数

给定两个正整数 ab,求他们的 最小公倍数(Least Common Multiple,LCM)。

思路很简单,两个数的最小公倍数等于他们的乘积除以最大公约数。

如果要求 多个数的最小公倍数 的话,跟「多个数的最大公约数」一样的思路,一个全局最小公倍数遍历所有数,来一遍最小公倍数。

这里可以有个小优化,先求个全局的最大公约数,然后每个数都除以最大公约数,再遍历新的数据求最小公倍数,最后乘上最大公约数,可以很大程度上节省求最大公约数的操作。