算法题中常用数学概念、公式、方法汇总（其三：数论）

数论

最大公约数

对于正整数$A$和$B$而言，若正整数$X$是同时能够被$A$和$$整除的最大正整数，则称$X$是$A$和$B$的最大公约数 （Greatest Common Divisor，GCD）

一般使用辗转相除法来求两个数的最大公约数，其流程如下

1. 规定两个数中的较大值和较小值分别为$A$和$B$，然后进行循环
2. 计算$X=A\%B$，其中$\%$为求余符号
3. 若此时$X=0$，则此时$B$是两数之间的最大公约数，退出循环
4. 若此时$X\ne 0$，则需要将$B$是两数赋值给$A$，余数$X$赋值给$B$，重复第二步

上述过程用代码表示为

def get_gcd(A, B):
    A, B = max(A,B), min(A,B)
    while A % B != 0:
        X = A % B
        A = B
        B = X
    return B

A, B = 144, 60
print(get_gcd(A, B))    # 输出12

在python中，math库中自带的gcd()函数，也可以直接计算两个数的最大公约数，其代码为

from math import gcd

A, B = 144, 60
print(gcd(A, B))        # 输出12

最小公倍数

对于正整数$A$和$B$而言，若正整数$Y$是同时能够整除$A$和$B$的最小正整数，则称$Y$是$A$和$B$的最小公倍数（Lowest Common Multiple,LCM）

已知一个正整数$A$和$B$的最大公约数为$X$，最小公倍数为$Y$，那么以下关系成立

$$X?Y=A?B$$

故求出正整数$A$和$B$的最大公约数为$X$，就可以求出最小公倍数$Y$。

$$Y=\frac{A?B}{X}$$

用代码表示为

from math import gcd

A, B = 144, 60
print(A * B // gcd(A, B))    # 输出720

*裴蜀定理

裴蜀定理，也称为贝祖定理（Bézout’s identity），指的是对于任意两个非零整数 a 和 b，存在整数 x 和 y，使得 ax + by = gcd(a, b)。

这个定理表明，对于任意两个整数，其最大公约数可以由它们的线性组合表示。其中，x 和 y 是整数系数，可以是正数、负数或零。

举个例子。考虑两个整数 a = 42 和 b = 30。a 和 b 的最大公约数为gcd(42, 30) = 6

那么我们可以找到(x, y) = (2, -3)，使得42x + 30y = 6成立。

题目LeetCode1250. 检查「好数组」就用到了裴蜀定理。我也贡献了一篇精华题解，感兴趣的同学可以看看这题。

质数

如果一个大于$1$的正整数$X$的因数只有$1$和他自身，那么称$X$为质数或素数（prime），否则称为合数（composite）。

特别规定：最小的质数是$2$。正整数$0$和$1$既不是质数也不是合数。

单个质数的判断

要判断一个正整数$X$是否为质数，最简单的方式就是枚举2到X-1的每一个数，检查这些数是否可以被$X$整除。如果出现了任何一个数可以被$X$整除，那么$X$是一个合数；反之$X$是一个质数。这种方法叫做试除法。

其代码实现如下

# 初始化一个标志，表示默认x是一个质数
isPrime = True
# 枚举从2到x-1的每一个数
for i in range(2, x):
    # 如果x可以整除i，说明x是合数
    if x % i == 0:
        isPrime = False
        break

# 退出循环后，根据isPrime的结果，可判断x是否是一个质数

上述过程的时间复杂度为O(x)。

实际上，由于一个正整数的因数总是成对出现的，无需枚举2到X-1的每一个数，只需要枚举枚举2到sqrt(X)就可以了。其证明如下：

假设 $X$ 是一个正整数且是合数，即 $X$ 可以被分解为两个正整数 $a$ 和 $b$，其中 $1<a\le b<X$。那么至少其中一个数一定小于等于 $\sqrt{X}$ ，另一个数一定大于等于 $\sqrt{X}$，即 $1<a\le \sqrt{X}\le b<X$。因此只需要枚举到$\sqrt{X}$，找到正整数 $a$ 即可。

其代码实现如下

from math import sqrt, floor

# 初始化一个标志，表示默认x是一个质数
isPrime = True
# 枚举从2到floor(sqrt(x))的每一个数
# 注意此处使用了向下取整
for i in range(2, floor(sqrt(x))+1):
    # 如果x可以整除i，说明x是合数
    if x % i == 0:
        isPrime = False
        break

# 退出循环后，根据isPrime的结果，可判断x是否是一个质数

上述过程的时间复杂度为O(sqrt(x))。

质数筛

上一小节主要讲解了单个正整数X的质数判断。如果将问题转变为小于等于N的所有正整数的质数判断，则需要用到质数筛。所谓质数筛，指的是类似筛子一样，可以高效地把合数过滤掉，留下质数。

质数筛分为埃氏筛（Sieve of Eratosthenes）和欧拉筛（Sieve of Euler），其本质大同小异。

埃氏筛

埃氏筛基于以下原理：假设 $X$ 是一个质数，那么 $X$ 的正整数倍 $2X$，$3X$，…， $mX$是一个合数。

因此我们需要构建一个长度为n+1的数组sieve，初始化sieve[x]均为True，表示默认正整数x为质数。

枚举从2到floor(sqrt(x))的每一个正整数数x。若

• x是质数，即sieve[x] == True。则再次进行内层循环，将x的m倍（m >= 2）均筛选出来，在数组sieve中标记为合数。
• x是合数，即sieve[x] == False，则直接跳过。

其代码实现如下

from math import sqrt, floor

def sieve_of_eratosthenes(n):
    # 构建埃氏筛，长度为n+1，初始化均为True，表示默认为质数
    sieve = [True] * (n + 1)
    # 0和1不是质数
    sieve[0], sieve[1] = False, False  
    # 枚举从2到floor(sqrt(x))的每一个数x
    for x in range(2, floor(sqrt(n))+1):
        # 如果x是一个质数，则说明其m倍（m >= 2）的所有正整数是合数
        if sieve[x] == True:
            # 将mx标记为False
            for i in range(2*x, n + 1, x):
                sieve[i] = False
                
    # 退出循环后，sieve中所有为True的元素下标为质数
    primes = [i for i in range(n + 1) if sieve[i]]
    return primes

筛选过程中，每个合数会被其最小质因数标记，对于小于等于 n 的合数，其最小质因数不会超过sqrt(n)。因此，对于每个质数 p，它标记的合数个数约为 n/p。

所以总的时间复杂度可以表示为：$O(n/2+n/3+n/5+...+n/p)$，其中 p 是不超过 n 的最大质数，这个求和可以近似为 $O(nlog(logn))$。

*欧拉筛

大部分时候，埃氏筛的时间复杂度已经足够接近线性时间复杂度 $O(n)$。但埃氏筛仍然存在优化空间。

比如合数6 = 2 * 3，既是质数2的正整数倍，也是质数3的正整数倍。在埃氏筛中，合数6会在考虑质数2和质数3的时候被重复筛选，这造成了额外开销。

为了避免同一个合数被重复筛选，对于每一个合数，我们希望只它被其最小的质因数筛选。

欧拉筛就是埃氏筛的改良算法，其具体过程如下：

构建一个长度为n+1的数组sieve，初始化sieve[x]均为True，表示默认正整数x为质数。另外构建一个primes数组，用于储存枚举过程中找到的质数。

枚举从2到n的每一个正整数数x，然后执行以下操作

• 若x是质数，即sieve[x] == True，则将x加入primes中。
• 无论x是质数还是合数，都再次枚举质数数组primes中的每一个质数p。考虑正整数x*p。若
  • 如果正整数x*p超过最大范围n，则可以直接枚举质数数组primes的循环。
  • p必然是合数x*p的最小质因数，将sieve[x*p]标记为False
  • 如果x是合数且是p的倍数，这表示x的最小质因数是p，x*p 的最小质因数也必然是p。如果x被p整除，并且继续用x的倍数标记后续的数，这些数会在后续的质数遍历中被重复标记，因为在之前的遍历中，x已经被p标记过了，所以在此处标记是多余的。因此，在发现x被p整除时，就可以中断对p的遍历，避免重复标记。

举个例子，当x = 4时，此时primes = [2, 3]。考虑p = 2，把x * p = 8标记为合数后，由于x % p == 0，可以直接退出循环，不用再考虑p = 3的情况，去标记x * p = 12。因为12会在后续的x = 6的时候，在考虑p = 2时被标记为合数。如果此时对4 * 3 = 12进行标记，会导致后续的6 * 2 = 12出现重复标记。

其代码实现如下

def sieve_of_euler(n):
    # 构建欧拉筛，长度为n+1，初始化均为True，表示默认为质数
    sieve = [True] * (n + 1)
    # 0和1不是质数
    sieve[0], sieve[1] = False, False
    # 构建质数数组，初始化为空
    primes = []
    # 枚举所有从2到n的正整数x
    for x in range(2, n + 1):
        # 如果x是质数，则加入primes数组中
        if sieve[x]:
            primes.append(x)
        # 无论x是不是质数，都枚举x的p倍，即正整数xp，其中p是已经筛选出的质数
        for p in primes:
            # 如果xp超过了n，则可以直接退出当前循环
            if x * p > n:
                break
            # p必然是合数xp的最小质因数
            # 将xp标记为合数
            sieve[x * p] = False
            # 如果x是合数且是p的倍数，则可以直接退出当前循环
            if x % p == 0:
                break
    return primes

由于每一个数，最多只会被标记一次。所以欧拉筛的时间复杂度为 $O(n)$。由于是线性的时间复杂度，欧拉筛也被称为线性筛。

多数情况下，更易于理解的埃氏筛已经足够优秀了，大家可以只掌握埃氏筛的方法。

---

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

• 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

• 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

• 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

• 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

• 绿色聊天软件戳 od1336了解更多