找质数，不止暴力试除——埃拉托色尼筛法与线性筛

找质数，不止暴力试除——埃拉托色尼筛法与线性筛，从入门到精通

写在前面

质数这玩意儿，从小学就开始打交道了。但直到我学算法的时候才发现，找质数这件事远不是从2试到n那么简单。

面试的时候被问过：怎么找出1到100万之间的所有质数？如果你回答每个数都试除一下，面试官可能会礼貌地点点头，然后在心里给你打个低分。因为对于大范围的质数筛选，有一种古老而优雅的算法——埃拉托色尼筛法，它的效率比暴力法高出几个数量级。

这篇文章我会从最基本的暴力试除讲起，逐步深入到埃氏筛、优化版埃氏筛，最后讲到线性筛（欧拉筛）。每种算法都配上代码、复杂度分析和图解。看完这篇，找质数这件事你就算彻底毕业了。

一、暴力试除：最朴素的想法

先别急着看筛法，咱们从最基础的写法开始。判断一个数 n 是不是质数，最直观的想法就是：从 2 到 n-1，看看有没有能整除 n 的数。

defis_prime(n):ifn<2:returnFalseforiinrange(2,n):ifn%i==0:returnFalsereturnTruedeffind_primes_bruteforce(n):return[iforiinrange(2,n+1)ifis_prime(i)]

这个写法的时间复杂度是 O(n^2)，找 1 到 n 的所有质数需要 O(n^2) 的时间。稍微优化一下，我们只需要试除到 sqrt(n) 就行了——因为如果 n 有一个大于 sqrt(n) 的因子，那它必然对应一个小于 sqrt(n) 的因子。

importmathdefis_prime_optimized(n):ifn<2:returnFalseforiinrange(2,int(math.sqrt(n))+1):ifn%i==0:returnFalsereturnTrue

优化后判断单个质数的时间复杂度降到了 O(sqrt(n))，找 1 到 n 的所有质数是 O(n*sqrt(n))。对于小数据量够用了，但如果 n = 10^6，这个算法就要算好几秒，根本没法用。

二、埃拉托色尼筛法：两千年前的大智慧

埃拉托色尼筛法（Sieve of Eratosthenes）是古希腊数学家埃拉托色尼在公元前3世纪提出的。它的核心思想非常巧妙：如果我知道一个数是质数，那它的所有倍数一定不是质数。

2.1 算法步骤

1. 列出从 2 到 n 的所有数
2. 从 2 开始，把 2 的所有倍数（4, 6, 8…）标记为合数
3. 找到下一个未被标记的数（3），把它的所有倍数标记为合数
4. 重复这个过程，直到处理完 sqrt(n) 为止
5. 剩下未被标记的数就是质数

我用一张图展示这个过程：

从图上可以看到，每找到一个质数 p，就把 p 的倍数全部筛掉。最终剩下的就是质数。

2.2 基础代码实现

defsieve_of_eratosthenes(n):# 初始化：假设所有数都是质数is_prime=[True]*(n+1)is_prime[0]=is_prime[1]=False# 从 2 开始筛p=2whilep*p<=n:ifis_prime[p]:# 从 p*p 开始标记，步长为 p# 为什么从 p*p 开始？因为 p*2, p*3... 已经被更小的质数筛过了foriinrange(p*p,n+1,p):is_prime[i]=Falsep+=1# 收集所有质数return[iforiinrange(2,n+1)ifis_prime[i]]# 测试print(sieve_of_eratosthenes(100))# 输出: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

2.3 复杂度分析

时间复杂度：O(n * log(log n))

这个复杂度看起来有点奇怪，怎么来的？简单解释一下：质数定理告诉我们，小于 n 的质数大约有 n / ln(n) 个。对于每个质数 p，我们需要标记 n/p 个倍数。总操作次数大约是：

n/2 + n/3 + n/5 + n/7 + ... ≈ n * log(log n)

空间复杂度：O(n)（布尔数组）

对于 n = 10^6，埃氏筛只需要几毫秒，而暴力法要好几秒。差距就是这么大。

三、埃氏筛的优化：还能更快吗？

基础版埃氏筛已经很快了，但还有几个优化点可以挖掘。

3.1 优化一：只筛奇数

除了 2 以外，所有偶数都不是质数。那我们干脆只存奇数，省一半空间。

defsieve_optimized(n):ifn<2:return[]# 只存奇数：索引 i 对应数字 2*i + 1size=(n+1)//2is_prime=[True]*size is_prime[0]=False# 1 不是质数# 从 3 开始，步长为 2（只处理奇数）forpinrange(3,int(n**0.5)+1,2):ifis_prime[p//2]:# 从 p*p 开始，步长为 2*p（只标记奇数倍数）foriinrange(p*p,n+1,2*p):is_prime[i//2]=Falsereturn[2]+[2*i+1foriinrange(1,size)ifis_prime[i]]

这个优化把空间 roughly 减半，实际运行速度也有明显提升。

3.2 优化二：分段筛

如果 n 非常大（比如 10^12），内存放不下整个数组怎么办？用分段筛。

思路是：先筛出 sqrt(n) 以内的所有质数，然后用这些质数去筛各个区间段。

defsegmented_sieve(low,high):# 分段筛：找出 [low, high] 区间内的所有质数limit=int(high**0.5)+1base_primes=sieve_of_eratosthenes(limit)# 标记当前区间的合数is_prime=[True]*(high-low+1)forpinbase_primes:# 找到第一个大于等于 low 的 p 的倍数start=max(p*p,(low+p-1)//p*p)forjinrange(start,high+1,p):is_prime[j-low]=False# 处理 low = 1 的情况iflow==1:is_prime[0]=Falsereturn[low+iforiinrange(len(is_prime))ifis_prime[i]]

分段筛的空间复杂度是 O(sqrt(n) + segment_size)，可以处理超大范围的质数查询。

四、线性筛（欧拉筛）：每个合数只筛一次

埃氏筛虽然高效，但有一个小缺陷：某些合数会被重复筛多次。比如 30 = 215 = 310 = 5*6，它会被 2、3、5 各筛一次。

线性筛（也叫欧拉筛）解决了这个问题：保证每个合数只被它的最小质因子筛一次。这样总操作次数严格是 O(n)，不会再有冗余。

4.1 核心思想

线性筛维护一个质数列表。对于每个数 i，用它去乘以已有的每个质数 p：

• 如果 i % p == 0，说明 p 是 i 的最小质因子，此时 break
• 否则，i * p 的最小质因子就是 p，标记 i*p 为合数

这样做的关键是：每个合数只被它的最小质因子筛一次。

4.2 代码实现

deflinear_sieve(n):# 线性筛（欧拉筛）# 时间复杂度: O(n)# 每个合数只被最小质因子筛一次is_prime=[True]*(n+1)is_prime[0]=is_prime[1]=Falseprimes=[]foriinrange(2,n+1):ifis_prime[i]:primes.append(i)# 用 i 乘以每个已知的质数forpinprimes:ifi*p>n:breakis_prime[i*p]=False# 关键：如果 p 是 i 的最小质因子，停止ifi%p==0:breakreturnprimes# 测试print(linear_sieve(100))

4.3 为什么线性筛是 O(n)？

关键在于那个 break。当 i % p == 0 时，p 是 i 的最小质因子。对于更大的质数 p2，i * p2 的最小质因子仍然是 p（因为 p 整除 i），所以 i * p2 应该由 p 来筛，而不是 p2。

这样每个合数只被筛一次，总操作次数就是 n 次，严格 O(n)。

五、三种算法综合对比

实际测试中（n = 10^7）：

• 暴力法：几十秒到几分钟
• 埃氏筛：约 1 秒
• 线性筛：约 0.5 秒

对于一般的面试题，写埃氏筛就够了。如果题目对性能要求极高，或者需要预处理大量质数，用线性筛。

六、质数在实际中的应用

质数不是纯数学玩具，它在计算机科学中有着广泛的应用：

6.1 RSA加密

RSA 是目前最常用的非对称加密算法之一。它的安全性基于一个数学事实：把两个大质数相乘很容易，但把乘积分解回两个质数极其困难。

RSA 的密钥生成过程：

1. 随机选两个大质数 p 和 q（通常几百位）
2. 计算 n = p * q
3. 公钥是 (n, e)，私钥是 (n, d)
4. 加密：c = m^e mod n
5. 解密：m = c^d mod n

没有私钥的人，要从 n 分解出 p 和 q，对于大数来说计算量是不可承受的。

6.2 哈希表容量

设计哈希表时，把容量设为质数可以减少冲突。因为质数和大多数数互质，散列分布更均匀。

6.3 伪随机数生成

线性同余生成器（LCG）中，模数 m 通常选大质数，这样生成的伪随机数周期更长、分布更均匀。

6.4 循环群与密码学

在模 p（p 为质数）的乘法群中，每个非零元素都有乘法逆元。这个性质在椭圆曲线密码学、Diffie-Hellman 密钥交换等算法中都有重要应用。

七、素数定理：质数有多稀疏？

你可能好奇：质数在整数中到底占多大比例？

素数定理告诉我们：小于 n 的质数个数大约是 n / ln(n)。也就是说，质数的密度随着 n 增大而逐渐降低，但永远不会消失。

可以看到，n/ln(n) 的近似效果随着 n 增大越来越好。这个定理也解释了为什么筛法比暴力法快那么多——因为质数越来越稀疏，需要标记的倍数也越来越少。

八、面试中的质数问题

面试中质数相关的题目通常有几种类型：

8.1 判断单个数是否为质数

写试除到 sqrt(n) 的版本就够了。注意处理 n < 2 的情况。

8.2 找出范围内的所有质数

写埃氏筛。如果面试官追问优化，提一下只筛奇数或者线性筛。

8.3 质因数分解

defprime_factorization(n):factors={}d=2whiled*d<=n:whilen%d==0:factors[d]=factors.get(d,0)+1n//=d d+=1ifn>1:factors[n]=factors.get(n,0)+1returnfactors# 测试: 360 = 2^3 * 3^2 * 5print(prime_factorization(360))# {2: 3, 3: 2, 5: 1}

8.4 第 k 个质数

用筛法预处理，然后直接查表。或者用二分 + 素数计数函数。

九、总结

找质数这件事，从暴力到筛法，体现了算法优化的核心思想：利用已知信息，避免重复计算。

• 暴力试除：逐个判断，O(n*sqrt(n))，适合单个质数判断
• 埃氏筛：质数的倍数标记合数，O(n*log(log n))，适合范围筛选
• 线性筛：每个合数只筛一次，O(n)，适合大范围/高频查询

面试建议：

1. 先写埃氏筛，这是标准答案
2. 主动提优化：从 p*p 开始、只筛奇数
3. 如果时间充裕，展示线性筛，体现深度
4. 了解质数的实际应用（RSA、哈希表），展示知识面

最后送一句话：质数就像编程里的基础工具，看似简单，但用好了能解决大问题。

如果这篇文章对你有帮助，欢迎点赞收藏！有任何问题可以在评论区留言，我会尽量回复。后续会持续更新算法相关的干货内容，欢迎关注！

本文原创，转载请注明出处。