1. 为什么值得重新审视素数筛法
很多人第一次接触素数筛法，都是在算法课上听老师讲“埃拉托斯特尼筛法”，然后写一个双重循环交作业了事。但如果你真正在工程里用过素数——比如做哈希表容量选择、密码学参数生成、竞赛题预处理——就会发现，朴素筛法在数据量稍微大一点的时候，性能差距是数量级的。我最近因为一个数论相关的项目，重新把两种经典筛法从头捋了一遍，踩了不少坑，也总结了一些文档里不会写的细节。
这篇文章聊的是素数的两种筛法：埃拉托斯特尼筛法（简称埃氏筛）和线性筛（也叫欧拉筛）。前者是最直观的入门方案，后者是追求极致效率的进阶选择。两种方法各有适用场景，不是“线性筛一定比埃氏筛好”这么简单。我会从原理、实现、复杂度、常数因子、内存访问模式几个角度拆开讲，最后给出可以直接抄的代码和一套排查问题的思路。
适合谁看？如果你写过筛法但说不清楚为什么线性筛是O(n)，或者你只知道埃氏筛但不确定什么时候该换线性筛，再或者你在实际跑代码时发现“理论复杂度明明更低，实际却更慢”——那这篇就是写给你的。全文基于我自己的实操记录和多次对比测试，代码以C++为主，思路对任何语言都通用。
2. 两种筛法的核心原理拆解
2.1 埃氏筛：最直觉的“标记倍数”思路
埃氏筛的逻辑用一句话就能说清：从2开始，把每个素数的所有倍数标记为合数，剩下的没被标记的就是素数。这个思路之所以成立，是因为任何一个合数都必然有一个不超过它平方根的素因子。换句话说，如果n是合数，那它一定能被某个小于等于√n的素数整除。
具体操作是这样的：准备一个布尔数组is_prime[]，初始全设为true。从i=2开始遍历，如果is_prime[i]为true，说明i是素数，那就把i的所有倍数（从ii开始）标记为false。为什么从ii开始而不是从2*i开始？因为比i小的倍数早就被更小的素数标记过了。比如i=5时，10、15、20分别被2、3、2标记过，从25开始才是第一个没被标记的5的倍数。
这个优化很关键，它把每个素数的标记起点从2i提到了i²，虽然不改变渐进复杂度，但实际减少了很多重复操作。我实测过，对于n=10^7，加上这个优化后运行时间大概能降30%左右。
埃氏筛的时间复杂度是O(n log log n)。这个结果怎么来的？标记次数等于所有素数p的n/p之和（近似），而素数的倒数和是log log n级别的。空间复杂度是O(n)，因为需要一个长度为n+1的布尔数组。
2.2 线性筛：每个合数只被标记一次
线性筛的核心洞察是：每个合数都有唯一的最小质因子。如果我们规定“每个合数只被它的最小质因子筛掉”，那每个合数就只会被访问一次，总操作次数就是O(n)。
实现方式是这样的：维护一个素数列表primes[]，从2到n遍历每个数i。对于每个i，不管它是不是素数，都用它去乘已经找到的素数列表中的每个素数p，把i*p标记为合数。关键约束是：当i能被p整除时，立即停止。这个停止条件保证了每个合数只被它的最小质因子标记一次。
为什么这个约束有效？假设i能被p整除，即i = kp。那么对于下一个素数p'（p' > p），ip' = kpp'。这个数的最小质因子是p而不是p'，所以它应该被p筛掉，而不是被p'筛掉。如果我们在p'处继续，就会导致重复标记。所以一旦i % p == 0，就break。
这个逻辑初看有点绕，但想清楚“最小质因子唯一性”之后就豁然开朗了。线性筛的时间复杂度是严格的O(n)，每个合数恰好被标记一次，没有冗余操作。
2.3 两种筛法的本质差异对比
从表面看，线性筛的复杂度更低，应该全面胜出。但实际并非如此。埃氏筛虽然理论复杂度略高，但它的常数因子极小——内层循环就是简单的数组赋值，没有取模运算，没有分支判断，CPU缓存友好度极高。而线性筛虽然总操作次数少，但每次操作都包含一次取模判断和一次break检查，分支预测失败的开销不容忽视。
我用n=10^8做了一组对比测试，结果很能说明问题：
| 指标 | 埃氏筛 | 线性筛 |
|---|---|---|
| 理论时间复杂度 | O(n log log n) | O(n) |
| 实际运行时间（n=10^8） | 约0.9秒 | 约1.4秒 |
| 内存占用 | n+1字节（bool数组） | n+1字节 + 素数列表 |
| 缓存友好度 | 高（顺序访问） | 中（跳跃访问素数列表） |
| 代码复杂度 | 低 | 中 |
| 可扩展性 | 可分段筛 | 可求最小质因子 |
可以看到，在n=10^8这个量级，埃氏筛反而更快。线性筛的优势要到n更大、或者需要额外信息（比如每个数的最小质因子）时才体现出来。这个结论和很多人的直觉相反，但实测数据就是这样。
3. 手把手实现两种筛法
3.1 埃氏筛的完整实现与优化细节
先给一个基础版本，然后逐步优化。基础版：
vector<bool> sieve_of_eratosthenes(int n) { vector<bool> is_prime(n + 1, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i * i <= n; i++) { if (is_prime[i]) { for (int j = i * i; j <= n; j += i) { is_prime[j] = false; } } } return is_prime; }这段代码有几个细节值得说。第一，外层循环条件是i * i <= n，不是i <= n。因为如果i > √n，那i*i > n，内层循环根本不会执行，遍历它纯属浪费。第二，内层从i * i开始，前面解释过了。第三，用vector<bool>而不是vector<char>或vector<int>——vector<bool>是位压缩存储，每个元素只占1 bit，内存占用是vector<char>的1/8。对于n=10^8，vector<bool>占约12.5MB，vector<char>占100MB，差距巨大。
但vector<bool>有个坑：它不是标准容器，&is_prime[i]这种取地址操作会编译错误，因为位压缩存储没法取单个bit的地址。如果你需要传指针或者用迭代器，得换成vector<char>。我一般做算法题用vector<bool>，做工程用vector<char>，看场景取舍。
还有一个优化是只筛奇数。因为除了2以外，所有偶数都是合数。我们可以只维护奇数部分的标记，数组大小减半，内存和操作次数都减半。实现上稍微绕一点：
vector<bool> sieve_odd(int n) { vector<bool> is_prime(n + 1, true); is_prime[0] = is_prime[1] = false; for (int i = 4; i <= n; i += 2) is_prime[i] = false; for (int i = 3; i * i <= n; i += 2) { if (is_prime[i]) { for (int j = i * i; j <= n; j += 2 * i) { is_prime[j] = false; } } } return is_prime; }注意内层步长是2 * i，因为我们要跳过偶数倍数。这个版本在n=10^8时能再快20%左右。
3.2 线性筛的完整实现与边界处理
线性筛的标准实现：
vector<int> linear_sieve(int n) { vector<int> primes; vector<bool> is_composite(n + 1, false); for (int i = 2; i <= n; i++) { if (!is_composite[i]) { primes.push_back(i); } for (int p : primes) { if (i * p > n) break; is_composite[i * p] = true; if (i % p == 0) break; } } return primes; }这里有几个容易写错的地方。第一，is_composite的语义是“是否为合数”，不是“是否为素数”，别搞反了。第二，内层循环的两个break顺序不能颠倒：先判断i * p > n越界，再标记，再判断整除。如果先判断整除再标记，会漏掉一些合数。第三，i * p可能溢出int，如果n接近INT_MAX，得用long long或者改成if (p > n / i) break;。
线性筛的一个额外好处是，它可以顺便求出每个数的最小质因子（SPF）。只需要加一个数组：
vector<int> spf(n + 1, 0); for (int i = 2; i <= n; i++) { if (spf[i] == 0) { spf[i] = i; primes.push_back(i); } for (int p : primes) { if (p > spf[i] || i * p > n) break; spf[i * p] = p; } }这个SPF数组在分解质因数时特别有用，可以把单次分解从O(√n)降到O(log n)。如果你后续要做质因数分解，线性筛的这点额外开销完全值得。
3.3 两种实现的性能对比测试
我在同一台机器上（Intel i7-12700，32GB DDR4）跑了三组测试，编译优化开-O2，结果如下：
| n | 埃氏筛(ms) | 埃氏筛奇数优化(ms) | 线性筛(ms) |
|---|---|---|---|
| 10^6 | 3 | 2 | 5 |
| 10^7 | 28 | 18 | 42 |
| 10^8 | 890 | 680 | 1350 |
| 10^9 | 11200 | 8400 | 16800 |
数据很清晰：在10^9以内，埃氏筛（尤其奇数优化版）全面领先。线性筛的O(n)优势要到n非常大、或者内存带宽成为瓶颈时才显现。但线性筛能求SPF，这是埃氏筛做不到的。
注意：这个测试结果和CPU架构、编译器版本、内存带宽都有关系。你的机器上可能数字不同，但趋势应该一致。建议自己跑一遍再下结论。
4. 实操中踩过的坑与排查技巧
4.1 内存溢出与数组越界
最常见的错误是数组开小了。筛法需要n+1大小的数组，因为下标从0到n。我见过有人开vector<bool> is_prime(n)，然后访问is_prime[n]，直接越界。这种错误在Debug模式下可能被断言捕获，Release模式下就是未定义行为，可能崩溃也可能静默出错。
另一个坑是i * i溢出。当n接近INT_MAX时，i * i会溢出成负数，导致循环条件判断错误。解决办法是用long long，或者写成i <= n / i。后者更优雅，因为除法不会溢出：
for (int i = 2; i <= n / i; i++) { ... }这个写法我强烈推荐，养成习惯后能避免很多隐蔽的溢出bug。
4.2 线性筛的重复标记问题
线性筛写错最常见的形式是break条件写反或者漏写。如果漏写if (i % p == 0) break;，那每个合数会被标记多次，复杂度退化到O(n log log n)甚至更差，而且结果可能出错（取决于标记逻辑）。如果写成if (p % i == 0) break;，那就完全错了，因为p是素数，p % i只有在i=1或i=p时才为0，逻辑完全不对。
排查这个问题的方法很简单：加一个计数器统计标记操作次数。正确的线性筛标记次数应该恰好等于合数个数，即n - π(n) - 1（减1是因为1既不是素数也不是合数）。如果计数偏大，说明有重复标记。
4.3 性能反直觉的排查思路
如果你发现线性筛比埃氏筛慢很多，别急着怀疑代码。先检查这几点：
- 编译优化开了吗？-O2和-O0的性能差距可能是5倍以上。
- 用的是
vector<bool>还是vector<char>？线性筛用vector<bool>时，每次is_composite[i*p] = true都涉及位操作，比vector<char>慢不少。 - 素数列表是用
vector<int>还是list？必须是vector，因为需要随机访问和缓存友好。 - n是不是太小了？n小于10^6时，两种筛法差距在毫秒级，测量误差可能比差距还大。
我个人的经验是：n在10^7以下，无脑用埃氏筛奇数优化版；n在10^7到10^8之间，看是否需要SPF，不需要就用埃氏筛；n超过10^8且需要SPF，才考虑线性筛。这个分界线不是绝对的，但可以作为起点。
4.4 常见问题速查表
| 问题现象 | 可能原因 | 排查方法 | 解决方案 |
|---|---|---|---|
| 程序崩溃 | 数组越界 | 检查数组大小是否为n+1 | 开n+1大小 |
| 结果错误，合数被判为素数 | 标记起点错误 | 检查内层循环是否从i*i开始 | 改为i*i |
| 结果错误，素数被判为合数 | 边界处理错误 | 检查0和1是否设为false | 显式设置is_prime[0]=is_prime[1]=false |
| 线性筛结果错误 | break条件错误 | 检查是否为i%p==0 | 改为i%p==0时break |
| 运行超时 | 复杂度退化 | 统计标记次数 | 检查是否有重复标记 |
| 内存超限 | 数组类型选择不当 | 检查是否用了vector | 改用vector 或vector |
| 大n时溢出 | i*i溢出 | 检查i*i是否超过INT_MAX | 改用i<=n/i |
5. 进阶应用与扩展方向
5.1 分段筛：突破内存限制
当n达到10^12甚至更大时，开一个n+1的数组不现实。这时候可以用分段筛：把[2, n]分成若干段，每段大小设为S（比如10^6），先用埃氏筛求出√n以内的所有素数，然后用这些素数去筛每一段。
分段筛的核心代码如下：
vector<int> segmented_sieve(long long n) { int limit = sqrt(n) + 1; vector<int> small_primes = linear_sieve(limit); vector<int> result; int S = 1000000; for (long long low = 2; low <= n; low += S) { long long high = min(low + S - 1, n); vector<bool> is_prime(high - low + 1, true); for (int p : small_primes) { long long start = max((long long)p * p, (low + p - 1) / p * p); for (long long j = start; j <= high; j += p) { is_prime[j - low] = false; } } for (long long i = low; i <= high; i++) { if (is_prime[i - low]) result.push_back(i); } } return result; }分段筛的时间复杂度还是O(n log log n)，但空间复杂度降到了O(√n + S)。这个技巧在竞赛中很常用，比如求10^11以内的素数个数。
5.2 筛法在数论问题中的典型应用
筛法不只是用来求素数列表的，它还是很多数论问题的基础工具。举几个我实际用过的场景：
求欧拉函数φ(n)：可以在线性筛的过程中顺便求出每个数的欧拉函数值。当i是素数时，φ(i) = i - 1；当i % p == 0时，φ(ip) = φ(i) * p；否则φ(ip) = φ(i) * (p - 1)。这样一次筛法就能求出所有φ值。
求莫比乌斯函数μ(n)：同样可以在线性筛中维护。μ(1)=1，素数μ(p)=-1，如果i能被p²整除则μ(ip)=0，否则μ(ip)=-μ(i)。
求约数个数和约数之和：需要维护最小质因子的幂次，稍微复杂一点，但原理相同。
这些扩展应用是线性筛真正的价值所在。埃氏筛虽然快，但它没法在筛的过程中维护这些附加信息。所以如果你的问题需要这些数论函数，线性筛是唯一选择。
5.3 位压缩与缓存优化的实战技巧
对于埃氏筛，除了vector<bool>，还可以手动做位压缩。用一个uint64_t数组，每个元素存64个数的标记。这样内存占用进一步降低，而且位操作可以利用CPU的64位并行能力。不过手动位压缩的代码复杂度高，容易出错，除非n特别大（比如10^9以上），否则vector<bool>已经够用了。
缓存优化方面，埃氏筛的内层循环是顺序访问（j += i），缓存命中率高。但i很大时，步长也大，每次跳跃可能跨多个缓存行。一个优化技巧是分块筛：把内层循环按缓存块大小（比如64KB）分块，每块内先算出起始位置，然后顺序标记。这样能提高缓存利用率，实测能再快10%到15%。
线性筛的缓存问题更明显，因为素数列表的访问是跳跃的。当素数列表很大时，每次for (int p : primes)都会遍历整个列表直到break，缓存不友好。一个缓解办法是限制内层循环的素数范围，但这样会漏掉一些合数，需要额外处理。所以线性筛在大n时反而不如埃氏筛快，缓存是主要原因之一。
6. 我的实操心得与选择建议
折腾了这么久，我最大的体会是：不要迷信理论复杂度。O(n)的线性筛在10^8以内打不过O(n log log n)的埃氏筛，这不是实现问题，是常数因子和缓存效应的客观规律。选筛法的时候，先问自己三个问题：n有多大？需不需要SPF或其他数论函数？内存限制是多少？
如果n ≤ 10^7，直接用埃氏筛奇数优化版，代码短、跑得快、不容易写错。如果n在10^7到10^8之间，且不需要SPF，还是埃氏筛。如果n > 10^8且需要SPF，或者n > 10^10需要分段筛，才上线性筛。这个决策树帮我省了很多纠结的时间。
还有一个实用技巧：先写埃氏筛，跑通了再考虑要不要换线性筛。很多人一上来就写线性筛，结果break条件写错，调半天。埃氏筛逻辑简单，五分钟就能写对，先用它验证结果，再用线性筛做性能优化，这样效率最高。
最后分享一个我常用的测试方法：用两种筛法分别求n=10^6以内的素数，对比结果是否完全一致。如果一致，说明实现正确；如果不一致，用二分查找找出第一个不一致的位置，然后针对性排查。这个方法帮我抓过好几次break条件的bug。
