从埃氏筛到线性筛：质数筛法的原理、优化与工程实践

1. "判断质数"和"筛质数"是两码事：从 O(√n) 到 O(n)

1.1 单个数判断的最朴素养子

我第一次接触质数筛法，是在想通一个问题之后：筛到底是什么意思？很多初学者（包括当年的我）刚上手时，以为"求质数"就是拿试除法一个一个判断。先写一个 is_prime 函数，对每个数字做整除测试，代码大概长这样：

def is_prime(n): if n < 2: return False i = 2 while i * i <= n: if n % i == 0: return False i += 1 return True

这个函数逻辑本身没问题：从 2 开始试除，只要碰到一个能整除的因子，n 就是合数。循环到 i*i > n 停止，是因为因子总是成对出现的，如果 n = a × b 且 a ≤ b，那么 a 必然不超过 √n。所以最多试到 √n 就足够了，单次判断复杂度是 O(√n)，听起来也不贵。

但问题是，现实题目很少只让你判断一个数。更多时候是"请输出 1 到 n 之间的所有质数"，n 动不动就是 10^7 甚至 10^8。这时候你如果对每个数都做一次试除，总复杂度就是 O(n√n)。10^7 个数、每个数最多试到约 3162 次，算下来是几百亿次取模运算，任何普通机器都扛不住。我第一次用暴力跑 n = 10^7 时，程序卡了快一分钟才出结果，那一刻我就明白：批量需求下，"判断质数"和"筛质数"完全是两种问题，后者必须换思路。

1.2 批量统计为什么必须换玩法

筛法的出发点很朴素：合数一定有某个更小的质因子。那就反过来，从最小的质数 2 开始，把它的所有倍数全部划掉；接着看 3，3 没被划掉，说明它是质数，再把 3 的所有倍数划掉；4 早就被 2 划掉了，跳过；5 没被划掉，是质数，继续划它的倍数……整个过程就像在一张名单上做排除法，最后没被划掉的数字，就是质数本身。这个"划掉"的动作，就是我们常说的"筛"。

我第一次跑通埃氏筛的时候，最大的感受是：原来遍历一批数字可以不用逐个验证，而是一次性把"非质数"全部标记出来。质数筛法的应用面也非常广，凡是需要提前准备一段质数表的问题，基本都靠它：数论题的预处理、欧拉函数和莫比乌斯函数的前缀和、质因数分解、哈希表容量选取，甚至 RSA 加密里的候选大质数预筛选，底层都有质数筛的影子。本文我会从埃氏筛讲到线性筛，再聊内存优化和实战选型，把我踩过的坑一并说出来。

2. 埃氏筛：从"划掉倍数"到第一版能跑的代码

2.1 筛法的直觉：一张名单，逐行划掉

埃拉托斯特尼筛法（Sieve of Eratosthenes）是公元前三世纪就出现的算法，今天依然是最基础的质数预处理方案。它的流程可以拆成四步：

1. 准备一个长度为 n+1 的布尔数组，初始全部标记为"是质数"；
2. 把 0 和 1 单独改成"不是质数"；
3. 从 2 开始向后遍历，遇到仍然标记为质数的 i，就把 i 的所有倍数标记为合数；
4. 遍历结束后，所有仍标记为质数的下标就是答案。

这里有一个必须理解的优化：标记倍数时，不要从 2 倍的 i 开始，而从 i 的平方开始。为什么？以 i = 7 为例，7×2、7×3、7×4、7×5、7×6 这些数字在更早的轮次里已经被 2、3、5 等更小的质数筛过了。比如 14 被 2 筛过，21 被 3 筛过，28 被 2 筛过。从 7×7 开始，就能避免这些毫无意义的重复标记。

2.2 外层循环为什么只走到 √n

这是另一个新手容易懵的地方：外层只需要遍历到 √n，后面的数字不用管了。原因在于，任何大于 √n 且小于等于 n 的合数，一定有一个不超过 √n 的质因子。既然它有一个小因子，那它在处理那个小因子时就已经被标记过了，根本轮不到后面的大数来筛。换句话说，筛到 √n 时，所有小于等于 n 的合数都已经"全部中招"，剩下的自然全是质数。

外层边界写得是否干净，直接影响性能和正确性。我后来在工程里见过不少为省事写成i < n的版本，虽然结果可能对，但白白浪费了后半段遍历；也有写成i * i <= n导致溢出的版本，这个具体放后面"踩坑"部分细说。

2.3 第一版代码与复杂度

一个标准、可以直接抄的埃氏筛，C++ 写成这样：

#include <vector> std::vector<int> sieve_of_eratosthenes(int n) { std::vector<char> is_prime(n + 1, 1); std::vector<int> primes; if (n >= 0) is_prime[0] = 0; if (n >= 1) is_prime[1] = 0; for (int i = 2; i <= n / i; ++i) { if (is_prime[i]) { for (long long j = 1LL * i * i; j <= n; j += i) { is_prime[(int)j] = 0; } } } for (int i = 2; i <= n; ++i) { if (is_prime[i]) primes.push_back(i); } return primes; }

这里我用了vector<char>而不是vector<bool>，后面会解释原因；外层用i <= n / i代替i * i <= n，纯粹是为了防 int 溢出，这两点都是实战里最常见的坑，先记住。

埃氏筛的时间复杂度是 O(n log log n)。怎么直观理解？内层对每个质数 p 大约要标记 n/p 个倍数，把所有质数加起来，总标记次数大约是：

n/2 + n/3 + n/5 + n/7 + n/11 + ...

质数倒数和收敛得非常慢，最终摊到 O(n log log n)。n 取 10^7 时，log log n 大概只有 2.8 左右，所以埃氏筛实际跑起来非常快。我第一次在 n = 10^7 上测，单核不到 100 毫秒，比暴力试除快了几百倍，那种痛快感直到现在都记得。

3. 线性筛（欧拉筛）：根治重复标记问题

3.1 重复标记到底浪费在哪

埃氏筛虽然快，但有一个理论上的瑕疵：同一个合数会被多个质因子重复标记。拿 12 举例，它会被 2 标记一次（2 的倍数里包含 12），又会 被3 标记一次（3 的倍数里也包含 12）。再比如 30 = 2×3×5，会被 2、3、5 各筛一次。合数越大，质因子越多，重复标记的次数也就越多。虽然这些重复操作摊到整体上不算夸张，但当你把 n 推到 10^8 甚至 10^9，重复标记带来的时间浪费就开始变得肉眼可见了。

线性筛，也常叫欧拉筛，要解决的核心问题就是这一个：让每个合数只被标记一次。于是它给自己定了一条铁律——每个合数只允许被它的最小质因子筛掉。只要做到这一点，标记总次数就是 O(n)，算法彻底线性。

3.2 break 条件的本质：最小质因子唯一性

线性筛的实现思路比埃氏筛多一个数组：维护一个 primes 列表，动态收集质数。主流程是：

1. 遍历 i 从 2 到 n；
2. 如果 i 没有被标记为合数，说明它是质数，加入 primes；
3. 不管 i 是不是质数，都拿 i 依次去乘 primes 里的每个质数 p，把 i×p 标记为合数；
4. 关键：当 i % p == 0 时，标记完 i×p 之后立刻 break。

这个 break 是整个算法的灵魂。为什么必须在 i 能被 p 整除时停下来？因为此时 i = p × k，那么对任意比 p 更大的质数 q，i×q = p × k × q，它是一个合数，而且它的最小质因子是 p，不是 q。如果现在用 q 去标记它，就违反了"每个合数只被最小质因子筛掉"的规则，将来它还会被另一个更大的 i 再筛一遍，那就退化成埃氏筛的重复标记了。

反过来，在 break 之前使用的那些 p，都是"不能整除 i"的质数。对这种 p，i×p 的最小质因子恰好就是 p，所以用它筛掉是合法的。而一旦遇到第一个能整除 i 的 p，就说明再往后的质数都不配给 i×p 当最小质因子了，必须交给将来的某个倍数关系去筛。这一下就把重复标记彻底掐死了。

3.3 完整代码与手推验证

#include <vector> std::vector<int> linear_sieve(int n) { std::vector<char> is_comp(n + 1, 0); // 0 表示未被标记，即认为是质数 std::vector<int> primes; for (int i = 2; i <= n; ++i) { if (!is_comp[i]) { primes.push_back(i); } for (int p : primes) { if (i * p > n) break; is_comp[i * p] = 1; if (i % p == 0) break; // 关键中的关键 } } return primes; }

这里我用 is_comp（is composite）而不是 is_prime，初值全 0 等价于"还没被标记为合数"，省掉一次重置。验证它是否真的做到"每合数只筛一次"，建议拿 n = 100 手推一遍：遍历到 i = 4 时，先用 p = 2 标记 8，然后 i % 2 == 0，break，所以不会用 p = 3 去标记 12；12 留到 i = 6、p = 2 时标记，标记完又 break，不会去碰 18；18 留到 i = 9、p = 2 时标记。每个合数都有且仅有一个"命中它的 (i, p) 组合"。

我实际调试线性筛时发现，最容易写错的地方是把 break 放到标记之前：

for (int p : primes) { if (i % p == 0) break; // 错误顺序 is_comp[i * p] = 1; }

这样会导致"当前 i 的最小质因子 p 与 i 相乘所得的合数"被漏标，后面的结果里混进一堆假质数。正确顺序一定是：先标记is_comp[i * p]，再判断i % p == 0决定要不要 break。这个顺序我至少写错过三次，每次都是靠 n = 100 的手算对照才发现。

3.4 线性筛真正的杀手锏：顺带算欧拉函数

很多人以为线性筛是为了比埃氏筛快，但实测里并非总是如此。线性筛内层有取模运算（i % p），而取模在 CPU 上是比较贵的操作；加上埃氏筛内层只是简单的加法步进，所以在只求质数列表这件事上，两者在 n = 10^8 级别往往各有胜负，有时候埃氏筛反而更快。

线性筛真正的价值，是它能借助"最小质因子"这条信息，在 O(n) 时间里顺带算出欧拉函数 φ、莫比乌斯函数 μ 等数论函数。埃氏筛做不到这件事，因为埃氏筛没有维护质因子关系。以欧拉函数为例，φ(i) 表示 1 到 i 中与 i 互质的数的个数，标准筛法如下：

const int MAXM = 10000000; long long phi[MAXM]; int primes[MAXM]; bool is_comp[MAXM]; int cnt = 0; void euler_sieve(int n) { phi[1] = 1; for (int i = 2; i <= n; ++i) { if (!is_comp[i]) { primes[cnt++] = i; phi[i] = i - 1; } for (int j = 0; j < cnt && 1LL * i * primes[j] <= n; ++j) { is_comp[i * primes[j]] = true; if (i % primes[j] == 0) { phi[i * primes[j]] = phi[i] * primes[j]; break; } else { phi[i * primes[j]] = phi[i] * (primes[j] - 1); } } } }

核心公式就两条：如果 p 已经整除 i，那么 i×p 的质因子集合没变，只是 p 的指数多了 1，所以 φ(i×p) = φ(i) × p；如果 p 不整除 i，那么 i×p 新增了一个质因子 p，φ(i×p) = φ(i) × (p-1)。单独对每个数硬算欧拉函数要 O(n√n)，用线性筛一次搞定，很多数论题靠的就是这个预处理。

4. 内存不是无限的：位压缩、跳过偶数与分段筛

4.1 用 uint64_t 手动位压缩

当 n 来到 10^9，直接用char数组标记，每个元素 1 字节，总共就需要 1GB 内存。这在许多场景下是致命的。最简单的优化是"一个二进制位管一个数字"：第 k 位为 1 表示 k 是合数，为 0 表示还没被标记。这样内存直接除以 8。C++ 里vector<bool>本身是位压缩的，但它有各种别扭（见第 5 节），所以追求可控时我更喜欢手动实现：

#include <vector> #include <cstdint> class BitSieve { std::vector<uint64_t> bits; public: explicit BitSieve(int n) { bits.resize((n >> 6) + 1, 0); set(0); set(1); } void set(int idx) { bits[idx >> 6] |= (1ULL << (idx & 63)); } bool test(int idx) const { return (bits[idx >> 6] >> (idx & 63)) & 1ULL; } };

每个 uint64_t 管 64 个数字，n = 10^9 时大约需要 10^9 / 8 ≈ 125MB。虽然比理想中的常数还大一些，但比 1GB 好太多了。Python 里也有类似思路：用bytearray(n+1)而不是list存布尔值。Python 的 bool 是对象，list 里一个元素先占 8 字节指针再加对象头，内存开销非常夸张；换成bytearray，每个元素 1 字节，n = 10^8 时内存从几个 GB 掉到 100MB，属于纯赚。

4.2 只存奇数，内存和耗时一起减半

另一个古老但有效的优化是：除了 2 以外的偶数都不是质数，干脆不存它们。数组下标做一次映射，下标 k 对应数字 2k+1，这样数组长度直接减半。标记倍数时，奇数 i 的倍数里，只有 i 乘奇数才是奇数，所以内层步长从 i 变成 2i：

std::vector<int> sieve_odd_only(int n) { int half = (n >> 1) + 1; std::vector<unsigned char> is_prime(half, 1); // is_prime[k] 表示数字 2k+1 是否为质数 for (int i = 3; i * i <= n; i += 2) { if (is_prime[i >> 1]) { for (long long j = 1LL * i * i; j <= n; j += 2LL * i) { is_prime[(int)(j >> 1)] = 0; } } } std::vector<int> primes; if (n >= 2) primes.push_back(2); for (int i = 3; i <= n; i += 2) { if (is_prime[i >> 1]) primes.push_back(i); } return primes; }

这个版本内存只有原始版的 1/2，标记次数也低很多，实测 n = 10^8 时耗时能压到普通埃氏筛的 60% 左右。它和位压缩是正交的，可以叠加使用：先只存奇数，再对半压缩，内存直接降到原来的 1/16。

4.3 分段筛处理 10^12 级别的大区间

有一种更彻底的内存解放方案：分段筛（segmented sieve）。它的适用场景很典型——要求 [L, R] 内的质数，R 巨大（比如 10^12），但区间长度 R-L 很小（比如 10^6）。这时候你完全没必要开一个长度为 R 的数组，只需要：

1. 先用普通埃氏筛筛出 [1, √R] 内的所有质数，这个范围很小（√(10^12) = 10^6），内存毫无压力；
2. 用这批小质数去标记 [L, R] 区间内的合数；
3. 剩余没被标记的，就是区间质数。

Python 实现如下：

def segmented_sieve(L, R): import math if L < 2: L = 2 base_primes = sieve_of_eratosthenes(int(math.isqrt(R)) + 1) is_prime = [True] * (R - L + 1) for p in base_primes: start = max(p * p, ((L + p - 1) // p) * p) for j in range(start, R + 1, p): is_prime[j - L] = False return [i for i in range(L, R + 1) if is_prime[i]]

start的计算是全程序最容易出错的地方。((L + p - 1) // p) * p是"大于等于 L 的最小 p 的倍数"，但还要和p * p取最大值，因为小于 p² 的合数已经被更小质因子筛过了。如果 L 很大，p * p在 C++ 里必须用 long long 装，否则又是一个溢出点。

分段筛还有一个额外好处：可以把大区间切成很多块，分给多台机器并行处理，每台机器只维护自己那一段的小数组。我在实际做并行质数统计时就靠它把 10^12 范围的筛分到了多个线程，每核内存占用稳定在几十 MB 以内。

5. 边界、溢出和 vector ：我实际踩过的坑

5.1 n 等于 0、1 时的处理

筛法代码最容易被边界条件阴到，尤其是 n 很小的时候。很多版本直接写is_prime[0] = false; is_prime[1] = false;，但如果你没先判断数组长度，n = 0 时访问is_prime[1]就直接越界了。稳妥做法是先判 n 的取值，小于 2 直接返回空数组；或者像我最开始给的模板一样，把对 0 和 1 的赋值分别用 if 包起来。这些细节平时不起眼，但一提交就红一片。

5.2 int 溢出和边界漏判

C++ 里i * i <= n是溢出重灾区。当 n 接近 2×10^9（接近 int 上限）时，i 到 46340 左右，i×i 已经逼近上限；再往下，i×i 直接变成负数，循环判断彻底崩坏，轻则死循环，重则访问非法下标。解决方式就是我在模板里写的：外层循环条件改成i <= n / i。这一步等价于i * i <= n，但全程不会溢出。

内层标记也有关键点：for (long long j = 1LL * i * i; j <= n; j += i)。如果 j 用 int，标记到后半段时 j += i 也可能溢出，所以把 j 设成 long long 再和 int 的 n 比较是习惯动作。另一个常见错误是循环条件写成j < n，把等于 n 的那个数漏掉。数组开到 n+1，循环就到<= n，这句要刻在脑子里。

5.3 vector 的代理对象和裸数组初始化

vector<bool>是 C++ 里一个著名的特例。它确实是位压缩的，但代价是v[i]返回的不是bool&而是代理对象（proxy reference）。这意味着你不能对它取地址，不能拿bool* p = &v[i]，很多需要指针传递的场景都会踩坑。如果只是为了省内存，又怕踩这些坑，我的建议是：优先vector<char>，内存不够再上vector<bool>或手写位压缩。

另一个内存相关的大坑是裸数组初始化。如果你写bool vis[n + 1];这种栈上数组，初值是不保证为 0 的，筛法基于"初始全部为质数"的假设直接崩盘。要么memset(vis, 0, sizeof(vis))，要么直接用容器并显式传初值。每次看到"筛出来的质数里混着合数"这类 bug，十有八九就是没有初始化。

6. 质数筛用在哪：竞赛、哈希表与加密预筛

6.1 竞赛里的典型姿势

算法竞赛里，质数筛几乎是数论题的基建工程。最常见的三个使用场景：

• 数论函数前缀和：需要计算 1 到 n 的欧拉函数和、莫比乌斯函数和时，线性筛一边筛质数一边算出函数值，总复杂度 O(n)，是标准解法；
• 大区间素数统计：题目给 [L, R] 让你统计区间内质数个数，R 大到数组装不下，就用分段筛；
• 质因数分解预处理：先把质数表筛出来，再对目标数逐个做短除法，拆解速度会快很多。

还有一类题是"判断大量 x 是否为质数"：先筛出 [1, max_x] 的标记数组，之后每个查询 O(1) 查表，这是最直观的打表思路。一旦你学会了线性筛顺带求 φ 和 μ，很多看起来复杂的数论题会瞬间降维。

6.2 工程场景：在 Miller-Rabin 之前的过滤

出了竞赛，质数筛也有实实在在的工程用途。最典型的是加密相关的候选大质数生成。RSA 需要找几十上百位的大质数，但没人会为 10^300 建数组——根本装不下。工程做法是：先快速生成一批小质数（比如 10^6 以内），用它们去试除候选大数，把能被小质数整除的候选提前淘汰；剩下没被淘汰的，再交给 Miller-Rabin 这类概率性素性检测做最终确认。这个"小质数预筛"阶段，用的就是最基础的质数筛法生成的质数表。

另一个常见场景是哈希表容量的选取。不少哈希表的实现会要求容量是质数，以减少哈希冲突。有些标准库在扩容时就查一张预先生成的质数表，这张表底层就是筛法跑出来的。再有就是科学计算里质数计数函数 π(n) 的验证、梅森素数搜索项目的区间预处理，原理也都离不开筛法。

6.3 一张表说清怎么选

我的习惯是"能埃氏就不线性，除非要顺带算数论函数"。这个原则可能跟很多人直觉相反，但埃氏筛代码短、好 debug，真实性能在线性筛面前并不吃亏。分段筛和位压缩是内存受限时的保命招，建议每个写算法的人都亲手实现一遍，因为它们是最考验边界处理细心的题材。

7. 调试验证与一份稳定跑了多年的模板

7.1 用 n = 100 手算做回归测试

无论你用哪种筛法，写完第一件事都该拿 n = 100 手算对照。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

一共 25 个。我调试那么多次，这个用例能一口气炸出至少三种问题：边界漏判（没有<= n）、break 顺序颠倒（漏标合数）、初始化错误（混入假质数）。不要嫌它简单，越简单的用例越能精准定位逻辑错误。

7.2 我给你准备的最终模板

如果现在让我手边放一份"拿来就能用"的 C++ 模板，我会这样写：

#include <vector> std::vector<int> sieve(int n) { std::vector<char> is_prime(n + 1, 1); std::vector<int> primes; if (n >= 0) is_prime[0] = 0; if (n >= 1) is_prime[1] = 0; for (int i = 2; i <= n / i; ++i) { if (is_prime[i]) { for (long long j = 1LL * i * i; j <= n; j += i) { is_prime[(int)j] = 0; } } } for (int i = 2; i <= n; ++i) { if (is_prime[i]) primes.push_back(i); } return primes; }

这个模板有三个关键点：vector<char>行为直白，不踩vector<bool>的代理对象坑；外层i <= n / i防溢出；内层long long j接住 i×i 再比较，同样防溢出。它在我打过的比赛、写过的工程里反复使用，没有出过问题。

7.3 我自己的选型收尾习惯

如果题目允许，我倾向于把"筛质数"和"后续任务"解耦：先单独筛出质数表，再在表上做各种数论计算。除非明确要求一次算出欧拉函数这类东西，否则我不会轻易上线性筛——不是它不好，而是埃氏筛的维护成本更低，新手看代码也更容易理解。等哪天你遇到内存吃紧、区间巨大、需要并行化这些场景，再回头把分段筛和位压缩拿出来，会更有体感。质数筛法这套东西，从理解到会用之间隔着好几次崩溃和调试，但每踩一次坑，后续的路都会更顺。