文章目录
数论最大公约数最小公倍数*裴蜀定理质数单个质数的判断质数筛埃氏筛*欧拉筛
华为OD算法/大厂面试高频题算法练习冲刺训练
数论
最大公约数
对于正整数
A
A
A和
B
B
B而言，若正整数
X
X
X是同时能够被
A
A
A和$
整除的最大正整数，则称
整除的最大正整数，则称
整除的最大正整数，则称X
是
是
是A
和
和
和B$的最大公约数 （Greatest Common Divisor，GCD）
一般使用辗转相除法来求两个数的最大公约数，其流程如下
规定两个数中的较大值和较小值分别为
A
A
A和
B
B
B，然后进行循环计算
X
=
A
%
B
X=A\%B
X=A%B，其中
%
\%
%为求余符号若此时
X
=
0
X=0
X=0，则此时
B
B
B是两数之间的最大公约数，退出循环若此时
X
≠
0
X\neq0
X=0，则需要将
B
B
B是两数赋值给
A
A
A，余数
X
X
X赋值给
B
B
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
A
A和
B
B
B而言，若正整数
Y
Y
Y是同时能够整除
A
A
A和
B
B
B的最小正整数，则称
Y
Y
Y是
A
A
A和
B
B
B的最小公倍数（Lowest Common Multiple,LCM）
已知一个正整数
A
A
A和
B
B
B的最大公约数为
X
X
X，最小公倍数为
Y
Y
Y，那么以下关系成立
X
∗
Y
=
A
∗
B
X*Y=A*B
X∗Y=A∗B
故求出正整数
A
A
A和
B
B
B的最大公约数为
X
X
X，就可以求出最小公倍数
Y
Y
Y。
Y
=
A
∗
B
X
Y=\frac{A*B}{X}
Y=XA∗B
用代码表示为
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
1
1的正整数
X
X
X的因数只有
1
1
1和他自身，那么称
X
X
X为质数或素数（prime），否则称为合数（composite）。
特别规定：最小的质数是
2
2
2。正整数
0
0
0和
1
1
1既不是质数也不是合数。
单个质数的判断
要判断一个正整数
X
X
X是否为质数，最简单的方式就是枚举2到X-1的每一个数，检查这些数是否可以被
X
X
X整除。如果出现了任何一个数可以被
X
X
X整除，那么
X
X
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
X 是一个正整数且是合数，即
X
X
X 可以被分解为两个正整数
a
a
a 和
b
b
b，其中
1
<
a
≤
b
<
X
1 1 X \sqrt{X} X ，另一个数一定大于等于 X \sqrt{X} X ，即 1 < a ≤ X ≤ b < X 1 1 ≤b X \sqrt{X} X ，找到正整数 a a 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 X 是一个质数，那么 X X X 的正整数倍 2 X 2X 2X， 3 X 3X 3X，…， m X mX 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 ) O(n/2 + n/3 + n/5 + ... + n/p) O(n/2+n/3+n/5+...+n/p)，其中 p 是不超过 n 的最大质数，这个求和可以近似为 O ( n l o g ( l o g n ) ) O(nlog(logn)) O(nlog(logn))。 *欧拉筛 大部分时候，埃氏筛的时间复杂度已经足够接近线性时间复杂度 O ( n ) O(n) 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 ) O(n) O(n)。由于是线性的时间复杂度，欧拉筛也被称为线性筛。 多数情况下，更易于理解的埃氏筛已经足够优秀了，大家可以只掌握埃氏筛的方法。 华为OD算法/大厂面试高频题算法练习冲刺训练 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！ 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！ 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 & OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多