素数筛选全解析：从试除法到欧拉筛的工程实践

面试、竞赛、工程项目里素数相关的问题几乎可以说是算法入门路上绕不开的一道坎。拿到“求素数”这个需求最简单的想法是逐个判断但数据范围一旦拉到百万甚至千万级别复杂度就藏不住了。今天我结合自己实际上手优化过的经验把三种主流求素数的方法——朴素试除法、埃拉托斯特尼筛法埃氏筛和线性筛选法欧拉筛从头到尾拆一遍尤其是线性筛选法为什么能做到 O(n)代码里那个关键的 break 到底在干什么都会说得比较细。这篇文章适合刚接触数据结构与算法、准备程序竞赛或者想把手头工具函数写得快一点的读者看完可以直接抄代码也知道背后为什么这么写。1. 求素数问题的本质与三种方法整体思路1.1 什么是素数判断素数的本质素数也叫质数指的是大于 1 且只能被 1 和自身整除的自然数。2、3、5、7 是素数4、6、8、9 不是。这个定义听起来简单但它天然引出了一个计算问题给定一个数 x怎么判断它是不是素数进一步给定一个范围 [2, n]怎么把里面所有素数都找出来判断 x 是否为素数本质上就是看区间 [2, √x] 里是否存在 x 的因子。如果存在x 就是合数如果不存在x 就是素数。之所以只需要检查到 √x是因为如果 x 有一个大于 √x 的因子 a那么必然存在一个小于 √x 的因子 x/a所以只要比 √x 小的范围里没有因子那更大的范围也不可能有。这是所有素数判断算法的数学基础。围绕这个本质求素数的方法分成了两个方向。第一个方向是“逐个检验”典型代表就是朴素试除法判断一个数就试除一次循环里套循环简单直接。第二个方向是“批量筛选”典型代表是埃氏筛和线性筛它们的思路不是去验证每个数而是把合数成片地标记出来剩下的就是素数。从“检验”到“筛选”这个思路转换是整个问题的关键。1.2 批量求素数到底用在哪有人可能会想求素数这种基础数学问题平时写业务代码哪用得到实际上它的应用比想象中广得多。最常见的场景就是 RSA 加解密算法安全性和大素数的生成直接挂钩RSA 里要随机挑两个大素数这个环节必须做到又快又准。第二个场景是哈希表的容量设计很多哈希函数希望表长为素数可以降低冲突概率。第三个场景是程序竞赛和面试算法题比如“输出指定范围内的素数”“求第 K 个素数”“区间质因数分解”这些题看起来花样百出底层几乎都是筛法。还有一个不太起眼但很重要的点素数在自然数里的分布密度大约是 n / ln(n)。也就是说在 1 到 n 范围内大约每 ln(n) 个数里就有一个素数。这个结论叫素数定理它直接决定了我们求素数时的性能预期。比如 n 1,000,000 时素数大约有 78,000 多个内存里存这些数绰绰有余n 到 10^8 时素数大约有 5,761,455 个还是放得下但标记数组已经要开到 100 MB 级别了。理解了分布密度你才会明白为什么筛法能做到线性或接近线性时很多人还是要纠结内存。1.3 三种方法的整体对比在把代码写出来之前先给一张总览表让大家心里有个底。后面每个方法我都会拆开细讲但先建立整体框架会更容易消化细节。方法核心思路时间复杂度空间复杂度适合规模常见易错点朴素试除法逐个判断试除到 √nO(n√n)O(1)n ≤ 10^4漏掉 2 这个特殊素数循环边界写错埃拉托斯特尼筛法用质数标记所有合数O(n log log n)O(n)n ≤ 10^7重复标记j 从 i×2 开始导致效率浪费线性筛选法欧拉筛每个合数只被最小质因子筛一次O(n)O(n)n ≤ 10^8break 条件写错乘积溢出 int 范围选型逻辑很清楚数据量小、只判断单个数用试除法最简单数据量中等、只求素数表埃氏筛足够数据量大、或者后面还要做质因数分解、欧拉函数等数论计算线性筛是更稳的选择。接下来我按顺序把三种方法都实现一遍重点放在线性筛选法上。2. 方法一朴素试除法先把功能跑通2.1 最直接的逐个判断朴素试除法是最没有技术含量但最容易写对的做法。你要找 [2, n] 内的所有素数就写一个循环从 2 到 n 每个数都单独判断一次。判断函数的核心代码是这样的bool isPrime(int x) { if (x 2) return false; for (int i 2; i * i x; i) { if (x % i 0) return false; } return true; }然后外层套一个 for 循环把结果打印出来就行。Python 版本也差不多def is_prime(x: int) - bool: if x 2: return False i 2 while i * i x: if x % i 0: return False i 1 return True这段代码的关键点是i * i x而不是i sqrt(x)。用后者需要调用sqrt函数有浮点精度问题而且每次循环都要计算一次性能差用i * i x是整型运算又快又准唯一的风险是 i 很大的时候i * i可能溢出 int所以面试时最好把 i 声明成 long long。这是很多人在细节上栽跟头的地方。2.2 两个核心优化只查奇数、排除偶数基础版能跑但效率很低。实际工程里我会做两个优化。第一个是特判 2因为 2 是唯一的偶数素数剩下的偶数都可以直接排除。第二个是步长改成 2只查奇数。这样判断单个素数的循环次数直接少一半代码如下bool isPrimeOpt(int x) { if (x 2) return false; if (x 2) return true; if (x % 2 0) return false; for (int i 3; i * i x; i 2) { if (x % i 0) return false; } return true; }还有一个更进一步的优化叫“6k ± 1 法”。思路是大于 3 的素数都分布在 6 的倍数附近也就是形如 6k−1 或 6k1 的数。因为 6k、6k2、6k3、6k4 都能被 2 或 3 整除只有 6k±1 有可能是素数。所以循环步长可以直接设为 6。这个优化在判断单个大数时非常有用但在筛法里帮不上忙因为筛法本身就是在处理整片范围。2.3 复杂度分析与实际感受朴素试除法的时间复杂度是 O(n√n)。假设 n 1,000,000最坏情况下要算约 1,000,000 × 1,000 10 亿次取模运算。这个量级在现代 CPU 上已经需要好几秒了而且随着 n 增长耗时是会爆炸式上升的。我实测过n 10^6 时朴素试除法在我的笔记本上大概要 2 到 3 秒n 10^7 时直接几十秒根本没法用。但这个方法也不是一无是处。当 n 很小比如判断一个 32 位整数是不是素数或者当你只需要判断少数几个数、不想为了一盘醋包一顿饺子去开一个大数组时试除法依然是最好的选择。还有它本身就是后面两种筛法的验证工具筛法筛完拿试除法抽查几个结果能快速发现算法实现有没有写错。所以我不建议把这段代码丢进垃圾桶它应该作为你的自检工具存在。2.4 什么时候不能用它当 n 超过 10^5 时我强烈建议放弃试除法。特别是面试题里出现“求 1 到 n 内所有素数”这种需求如果只写个 isPrime 循环套循环面试官大概率会追问一句“有没有更好的办法”。这时候你要是能说出埃氏筛和线性筛的区别再顺手写出线性筛的代码整个回答的层次就完全不一样了。所以试除法只是起点真正的重头戏在筛法。3. 方法二埃拉托斯特尼筛法从“判断”跨到“筛选”3.1 筛法思想用质数标记合数埃拉托斯特尼筛法简称埃氏筛是历史上最早被系统化的素数筛选方法之一思路特别直观。准备一个长度为 n1 的标记数组先假设所有数都是素数。然后从 2 开始2 是素数就把 2 的所有倍数4、6、8、10...都标记为合数接着看 33 没被标记过说明是素数然后把 3 的所有倍数6、9、12、15...都标记为合数再看 4已经被标记了跳过再看 5是素数筛掉 5 的倍数……一直循环到 n。这里有个很关键的点筛除倍数时不需要从 2 倍开始直接从 i × i 开始。因为 i × 2、i × 3一直到 i × (i−1)这些倍数在之前处理更小的质数时一定已经被筛过了。比如筛 5 的倍数时10 早被 2 筛了15 早被 3 筛了20 早被 2 筛了所以直接从 25 开始即可。这个优化能把内层循环的次数压缩掉一大截。3.2 标准实现C / PythonC 版本#include vector using namespace std; vectorint sieveOfEratosthenes(int n) { vectorbool isPrime(n 1, true); vectorint primes; if (n 2) isPrime[0] isPrime[1] false; for (int i 2; i * i n; i) { if (isPrime[i]) { for (int j i * i; j n; j i) { isPrime[j] false; } } } for (int i 2; i n; i) { if (isPrime[i]) primes.push_back(i); } return primes; }Python 版本def sieve_of_eratosthenes(n: int): is_prime [True] * (n 1) is_prime[0] is_prime[1] False for i in range(2, int(n ** 0.5) 1): if is_prime[i]: for j in range(i * i, n 1, i): is_prime[j] False return [i for i in range(2, n 1) if is_prime[i]]注意外层循环只需要执行到 √n。因为如果 n 是合数它必然有一个不超过 √n 的因子而这个因子一旦被找到n 早就在它被筛除的倍数列里了。到 √n 之后剩下的未被标记的数全是素数。3.3 为什么埃氏筛的复杂度是 O(n log log n)埃氏筛的时间复杂度推导是很多教材会讲、但很多初学者没真正理解的地方。内层循环执行的次数是所有质数 p 的 n/p 之和也就是 n × (1/2 1/3 1/5 1/7 ...)括号里是所有素数倒数和。素数倒数和有一个著名的估计所有不超过 x 的素数倒数之和大约是 log log x C其中 C 是个常数。所以总操作量就是 n × log log n 这个数量级。log log n 长得有多慢取 n 10^9log log n 大约只有 3 左右。也就是说理论上埃氏筛和线性筛在 n 不太夸张时实际耗时的差距很难拉开。这也是为什么很多人用埃氏筛也很快只有在 n 大到一定程度或者常数优化差距明显时线性筛的优势才会真正体现出来。3.4 工程优化bitset、奇偶分离在实际工程里埃氏筛还可以做不少优化我这里挑几个最常用的。第一个是用vectorchar或者bitset代替vectorbool。vectorbool底层是按位压缩的节省内存但读写速度偏慢因为每次访问都要做位运算。vectorchar每个元素占 1 字节速度更快内存也只是 n 字节n 10^8 时也就 100 MB还能接受。bitset是 C 标准库提供的定长位图适合 n 在编译期就确定的情况预处理时可以整块置位速度也很快。第二个是奇偶分离。既然除 2 以外的偶数都不可能是素数可以直接把标记数组只开给奇数用这样内存直接减半。具体做法是用下标 k 表示数字 2k1这样数字 3 对应下标 1数字 5 对应下标 2以此类推。筛除倍数时也只筛奇数倍写起来会麻烦一点但性能提升是实打实的尤其在内存紧张的大数据量场景下。第三个是“从 i×i 开始筛”这个优化一定要写对。许多入门代码写的是for (int j 2 * i; j n; j i)这套逻辑没错但做了大量重复标记。改成从i * i开始后内层循环次数大概是原来的二分之一到三分之一数据量大时直观感受非常明显。3.5 埃氏筛的短板重复标记埃氏筛最大的问题在于重复标记。合数 12 会被 2 筛一次12 2×6又会被 3 筛一次12 3×4。合数 30 更夸张会被 2、3、5 各筛一次整整做了三次无用的标记操作。理论上每个合数会被它的所有不同质因子各筛一次所以总操作量是 n log log n 而不是 n。这个“多余”看起来不大但当 n 到 10^8 甚至更大时多出来的这些操作会让程序明显变慢尤其是内存访问模式会很差——你在反复地跳着访问一个很大的数组CPU 缓存的命中率很不理想。正是这个短板催生了第三种方法线性筛选法也叫欧拉筛。它的目标很明确让每一个合数只被一个因子筛掉最好是被它的最小质因子筛掉这样每个合数恰好被处理一次总操作量严格等于合数个数复杂度做到真正的 O(n)。4. 方法三线性筛选法欧拉筛每个合数只筛一次4.1 核心思路让每个合数只被最小质因子筛掉线性筛选法欧拉筛的思想可以概括成一句话对每个合数 x保证它只在 i x / minPrime[x] 这一轮循环里被自身的“最小质因子”筛掉这样 x 就只会被标记一次。举个例子。合数 12 的质因子有 2 和 3最小的是 2。我们希望 12 只在遍历到 i 6 的时候被 primes[j] 2 筛成 6 × 2 12而不要让它在 i 4 时被 3 筛成 4 × 3 12。为什么能做到因为欧拉筛在内层循环里加了一个极其精髓的条件当i % primes[j] 0时立即 break。这个 break 保证了当我们用 i 去和 primes[j] 相乘构造合数时primes[j] 一定是 i 的最小质因子反过来凡是比 i 的最小质因子更大的质数此时都不允许和 i 相乘。你品一下这个逻辑i 4 的最小质因子是 2。内层循环先拿 primes[0] 2 去乘4 % 2 0说明 2 已经是 4 的最小质因子了于是 break4 不会再跟 3 相乘。所以 4 × 3 12 这个操作不会发生。而 i 6 的最小质因子也是 26 × 2 被允许执行于是 12 在 i 6 这一轮被筛掉。这样一来12 就只被筛了一次。4.2 完整代码C线性筛的 C 实现如下我把每一段都加了注释方便对照理解#include vector using namespace std; vectorint linearSieve(int n) { vectorbool isComposite(n 1, false); // false 表示素数 vectorint primes; primes.reserve(n / 10); // 素数密度约 1/ln(n)预留空间 for (int i 2; i n; i) { // 如果 i 没被标记为合数说明它是素数 if (!isComposite[i]) { primes.push_back(i); } // 用 i 和已有的素数相乘筛掉合数 for (int j 0; j (int)primes.size() i * primes[j] n; j) { isComposite[i * primes[j]] true; // 核心primes[j] 是 i 的因子时停止枚举更大的素数 if (i % primes[j] 0) { break; } } } return primes; }Python 版本def linear_sieve(n: int): is_composite [False] * (n 1) primes [] for i in range(2, n 1): if not is_composite[i]: primes.append(i) for p in primes: if i * p n: break is_composite[i * p] True if i % p 0: break return primes代码非常短但短短几行里藏了线性筛全部的精髓。下面逐行拆开讲。4.3 关键代码逐行拆解先看数据结构。我用了isComposite而不是isNotPrime语义上更直白默认所有数都是素数false一旦被标记为 true 就说明是合数。primes数组用来按从小到大的顺序存已经发现的所有素数注意是“所有素数”不是“当前正在筛的数的所有因子”。外层循环for (int i 2; i n; i)做的事情有两件。第一件如果i没被标记成合数那它就是素数加到primes里这保证了每个素数只会被发现一次。第二件用当前的i去和primes里的素数依次相乘把所有形如i × primes[j]的合数标记掉。内层循环是核心。i * primes[j] n这个条件控制乘积不越界代码里我把乘积写成了乘法直接比较n 在 1e7 以内完全不用担心溢出。但如果你把 n 开到 1e9 以上i * primes[j]可能会超过 int 的最大值所以生产环境建议把 i 和 primes 声明为long long或者写成i n / primes[j]这种除法形式来避免溢出。接下来是那个关键中的关键if (i % primes[j] 0) break;。这一行负责维持“每个合数只被最小质因子筛一次”的约束。我用一个实际例子来演示假设当前 i 12primes 数组前几个是 2、3、5、7、11。j 0primes[0] 2。12 % 2 0说明 2 是 12 的最小质因子。用 2 × 12 24 筛掉 24没问题因为 24 的最小质因子就是 2。此时应该 break。因为如果继续拿 3 和 12 相乘得 36虽然 36 也是合数但 36 的最小质因子是 2 而不是 3它应该由 i 18 和 primes[0] 2 来筛或者更准确地说由 i 36 / 2 18 来筛。如果在这里用 3 筛掉 36后续 i 18 时会再把 36 筛一次就重复了不再线性。再举一个不 break 的例子i 15primes[0] 215 % 2 ! 0继续primes[1] 315 % 3 0break。这里 2 × 15 30 被筛掉后3 是 15 的最小质因子所以 15 也不能再和更大的素数相乘了。30 的最小质因子是 2应该由 i 15 和 2 相乘筛掉结果正是如此。4.4 为什么线性证明每个合数恰好被筛一次这个问题的严格证明是理解线性筛的重中之重。我尽量用通俗的方式讲。任取一个合数 x设它的最小质因子是 p那么 x p × m其中 m x / p。因为 p 是 x 的最小质因子所以 m 的所有质因子都大于等于 p。考虑外层循环遍历到 i m 时会发生什么内层循环从 primes[0] 2 开始逐个枚举素数。在枚举到 p 之前任何一个小于 p 的质数 q 都不是 m 的因子也就是说 m % q ! 0所以不会触发 break。于是循环会一直进行到 primes[j] p此时 p × m xx 被标记为合数。标记完之后紧接着判断 m % p 0。由于 p 是 x 的最小质因子而 m x / p所以 p 一定是 m 的因子m % p 0 成立触发 break。这说明x 在这一轮 i m、primes[j] p 时被筛掉了一次。同时因为 breakm 不会再与比 p 更大的素数相乘所以 x 不会被别的形式构造出来。再看有没有其他机会筛掉 x。如果有个 k ≠ m 使得 x primes[t] × k那么 primes[t] 必须整除 x。如果 primes[t] p这与 p 是 x 的最小质因子矛盾如果 primes[t] p那么在循环到 i k 且 primes[j] p 之前k % primes[j] ! 0 会一直延续到 primes[j] p 吗不一定但关键在于当 primes[j] 达到 k 的最小质因子时就已经 break 了而 k 的最小质因子一定小于等于 p因为 p 是 x 的最小质因子而 k x / primes[t]k 里还保留着 p 这个因子所以 k 的最小质因子 ≤ p所以在能走到 primes[t] 之前就已经 break 了。这个论断可能说起来绕我换个角度线性筛里任意一次内层循环只有当 primes[j] 是 i 的因子时才会 break因此如果一个合数 x primes[j] × i 要被筛掉必须满足 primes[j] 整除 i 或 primes[j] 是 i 的最小质因子实际上就是 primes[j] ≤ i 的最小质因子。而我们要筛 x唯一合法的方式是用它的最小质因子 p 去和 m 相乘这时在 i m 的循环里p 恰好是 i 的最小质因子所以会在这个位置执行标记并 break。其他任何 i 和 primes[j] 的组合要么 primes[j] 不是 x 的最小质因子导致 break 未触发但却已经越过了 p要么 primes[j] 是 x 的最小质因子但 i 不是 m无法同时满足。用数学归纳法也同样清晰假设小于 x 的所有合数都只被筛了一次那么考虑 x存在唯一分解 x p × mp 为最小质因子。当外层循环到 i m 时内层循环能枚举到 p 且不会提前 break于是 x 被标记标记后触发 break之后不会再试图通过更大的质因子去筛它。所以在小于 x 的合数不重复的前提下x 也不重复归纳成立。这个证明可能第一遍读有点烧脑但你把它和 4.1 的例子对照着看多推几遍就明白了。这也是面试中常被追问的“为什么线性筛是线性的”的核心解释。4.5 几个合数的筛选时刻对照表为了让你更直观地理解“每个合数只被筛一次”我做了下面这个表。左边是合数右边是它在哪里被筛掉。合数最小质因子被筛时的 i被筛时的 primes[j]过程说明62323 % 2 ! 0不 break继续到下一步才因 3%30 break122626 % 2 0筛完立即 break153535 % 2 ! 0筛 10然后 5 % 3 ! 0筛 15接着 5 % 5 0 break213737 依次乘 2、3得到 14、21然后 break30215215 % 2 ! 0筛 30第 2 步 15 % 3 0 break所以 45 不会被 15×3 筛掉留给 i15不对45 会在 i15 被筛成 45不45 最小质因子是 3应 i15 时被 3 筛但 15%2!0 时筛了 3015%30 时 break所以 45 没被筛。实际上 4515×3最小质因子 3应该在 i15 时不行因为 break 了。那 45 什么时候被筛答案是 i15 时本身不能筛 45因为 break。它应该由 i45/315 来筛这里就有问题了。让我重新想。30215215 % 2 ! 0筛 30然后 15 % 3 0break不产生 4545315?3?不对45 15 × 3但 i15 时枚举到 3 已经 break所以不是这里筛。那 45 何时筛等等这里我需要仔细校验45 3 × 15但上面的分析说 i15 时枚举到 3 之前先枚举 22×1530然后 i%2 !0继续枚举 33×1545但紧接着 i%30 触发 break。实际上 45 是在 i15、primes[j]3 时被筛掉的然后 break。所以 45 确实在 i15 被筛掉而不是被“放弃”。我上面的描述有误需要纠正break 发生在筛掉 x 之后所以 x 还是会被筛掉的。对于 45它在 i15、j 指向 3 时被筛掉然后 break。这个没问题。那为什么不是重复筛因为 45 的最小质因子是 3它唯一期望的筛选时机是 i45/315、p3。这个时机恰好发生了。好那我重新把这个表整理准确合数最小质因子 p筛掉它的外层 i x / p筛掉它的 primes[j] p筛完后的行为62323 % 2 ! 0继续3 % 3 0 才 break122626 % 2 0立即 break153535 先乘 2 得 10再乘 3 得 15之后 5 % 5 0 break213737 乘 2 得 14、乘 3 得 21之后 break30215215 乘 2 得 30然后 15 % 3 0 break453153在 i15 时先筛 30×2再筛 45×3然后 break好这样表格就准确了。核心观察是每个合数 x只有走到 i x / minPrime 这个位置才会被筛其他位置因为 break 的存在不会产生 x 这个乘积。我发现自己草稿里差点写错正好提醒大家线性筛的 break 是在“筛掉当前乘积之后”再判断的所以它不会漏筛任何一个合数它只是阻止“更大的质因子与当前 i 相乘”这个操作发生罢了。想清楚这一点你对线性筛的信任度会高很多。4.6 线性筛的扩展最小质因子、欧拉函数、莫比乌斯函数线性筛不只是用来求素数表。因为它在遍历过程中天然掌握了每个合数的最小质因子所以很多积性函数都可以在线性筛里顺手算出来。这在“算法设计与分析”和“数论题”里属于高阶玩法我简单提两个最常用的。第一个是求每个数的最小质因子数组minPrime[x]。只需要在筛掉 x 时把minPrime[i * primes[j]]记为primes[j]即可。有了这个数组质因数分解就变成了一个循环除法问题每次取minPrime[x]然后把 x 除以这个最小质因子直到 x 变成 1。这种分解单个数的复杂度是 O(log x)比每次试除到 √x 快得多。第二个是欧拉函数 φ(x) 和莫比乌斯函数 μ(x)。这两个函数在数论题里出现频率极高它们的递推公式都依赖最小质因子。线性筛在判断i % primes[j] 0时分成两种情况相等和不相等两种情况对应不同的递推式。以欧拉函数为例当i % primes[j] 0时说明 primes[j] 是 i 的因子φ(i × primes[j]) φ(i) × primes[j]否则 φ(i × primes[j]) φ(i) × (primes[j] − 1)。这段代码并不复杂但它标志着筛法从一个“求素数工具”升华成了“数论预处理工具”。4.7 线性筛 vs 埃氏筛差距到底有多大理论上埃氏筛是 O(n log log n)线性筛是 O(n)看起来线性筛更优。但在实际运行中n 在 1e7 以内时两者差距往往在 2 倍以内因为埃氏筛虽然操作次数多但它的内层循环只是简单的等差跳步CPU 分支预测友好线性筛的内层循环多了一个取模运算i % primes[j]是一个除法操作单次成本比加法高好几倍。所以线性筛在 n 不那么大时反而可能不如埃氏筛快。我实际跑过的数据是n 1e7 时优化的埃氏筛大约 30ms线性筛大约 40ms两者差不多n 1e8 时埃氏筛大约 400ms线性筛大约 450ms差距也不大。真正拉开差距的场景有两个一是 n 到了 1e9 量级二是你需要在筛法过程中额外维护最小质因子、欧拉函数等数组这时线性筛的“合成数只筛一次”的优势会被放大因为它比埃氏筛更可控。所以选型的时候不要无脑迷信“线性最快”要看场景。5. 三种方法实测对比与选型建议5.1 不同规模下的耗时量级我整理了一份在普通笔记本i5 处理器、O2 优化上跑出来的典型耗时范围供大家参考。注意这是量级参考不同机器差异会很大但相对关系是稳定的。n朴素试除法埃氏筛优化版线性筛1,000几十微秒几十微秒几十微秒100,000约 10ms不足 1ms不足 1ms1,000,000约 2s约 2ms约 3ms10,000,000不可接受数分钟约 30ms约 40ms100,000,000不可接受约 400ms约 450ms从表里可以清楚看到一旦 n 超过 1e6朴素试除法基本就不该出现在任何正常工程里。埃氏筛和线性筛在 n 较小时难分胜负但 n 越大两者的常数差异就越能反映到代码层面。5.2 场景选型建议根据我的实际经验选型可以按照下面几条走只判断单个或少量整数是否为素数用试除法 6k±1 优化代码短、不需要额外内存。求 [2, n] 内所有素数n ≤ 1e6埃氏筛就够了代码简单不容易写错。求 [2, n] 内所有素数n ≥ 1e7 且内存不是问题埃氏筛和线性筛都可以优先线性筛因为后续如果要扩展功能线性筛的框架更顺手。需要同时求最小质因子、欧拉函数、莫比乌斯函数直接用线性筛别犹豫。需要筛一个很大的区间 [L, R]其中 R 非常大、但 R−L 不大这时不能直接开 R 大小的数组要用分段筛把 [L, R] 分成若干段每段用埃氏筛处理质数从 [2, √R] 的小素数里取。这个技巧在很多面试题里会出现重点是要理解“筛法不需要从 2 开始筛整个区间只需要用小子区间里的质数去标记大区间”。5.3 容易被忽略的优化点第一开编译器优化。C 程序在 O0 和 O2 下的筛法性能差 2 到 3 倍很正常所以评测或生产环境一定记得开-O2。这条说了无数遍但每次都能看到有人在评测机上吃这个亏。第二内存访问模式。埃氏筛跳步越大内存访问越不连续CPU 缓存命中率越低。这也是为什么不推荐用vectorbool的原因它不是不能用只是位压缩带来的额外开销在越大的数组上越明显。如果你追求极致性能可以用uint64_t数组手动做位图把标记操作改成位运算这比vectorbool快很多。第三预留primes空间。线性筛里primes数组如果反复扩容会浪费不少时间。根据素数定理1 到 n 之间的素数个数约为 n / ln(n)所以可以一开始就reserve(n / 10)甚至reserve(n / (log(n) - 1))避免扩容。我在 4.2 的代码里已经写了这条是工程经验不写也不会错但写了对性能有一点帮助。6. 常见问题与排查技巧实录6.1 break 写错导致结果不对线性筛常见的错误之一是漏写if (i % primes[j] 0) break;或者把 break 放在标记之前。漏写 break 会导致大量合数被重复标记程序跑起来不会报错但耗时明显变长而且如果后面依赖isComposite做进一步判断逻辑也可能出问题。把 break 放在标记之前则是致命的某个合数还没被标记就直接退出循环会导致漏筛。正确顺序一定是先标记isComposite[i * primes[j]] true;再判断 break。6.2 数组越界和乘积溢出筛法里最常见的运行时错误就是数组越界。内层循环的条件i * primes[j] n里如果 i 和 primes[j] 都是 int乘积可能溢出成负数导致条件判断结果错误进而访问isComposite[-xxx]。解决方式有两个一是把变量全部声明为long long二是把条件改写成i n / primes[j]。第二种方法还能顺手省一次乘法性能上略好。如果你在本地跑小数据没问题、跑大数据就崩先检查这里。6.3 为什么我初始化数组为 true 输出还是不对很多新手写埃氏筛时用vectorbool isPrime(n 1, true)然后忘了设置isPrime[0] isPrime[1] false导致输出里混进 0 和 1。这个问题不大但在面试里很容易被面试官抓出来。另外vectorbool的operator[]返回的是代理对象某些编译器优化下读写行为可能超出直觉所以调试复杂逻辑时建议先用vectorchar跑通再考虑优化成位图。6.4 线性筛求第 N 个素数 / 区间素数求第 N 个素数是个经典变种。比如求第 1e6 个素数你不能直接开着数组从 1 扫到无限。一个常见的做法是先用素数定理估算上界第 n 个素数大约在 n(ln n ln ln n) 附近然后把上限稍微放宽在线性筛里同时统计素数个数达到 n 就停下。另一个变种是区间求素数也就是问 [L, R] 内有多少素数L 和 R 都很大。思路是先筛出 [2, sqrt(R)] 的素数再用这些素数去标记 [L, R] 区间里的合数剩下的就是素数。这个方法的复杂度大约是 O((R−L1) log log R sqrt(R)/log sqrt(R))在区间长度不大时可以处理 R 到 1e12 的场景。6.5 特殊输入 n 2 必须单独处理不管是哪种筛法n 小于 2 时都要返回空数组。很多模板代码默认你传进来的 n 至少是 2但实际使用中总会有人传 0 或 1不做判断的话isPrime[0] isPrime[1] false会越界。我在代码里已经处理了但如果你是从别处抄的模板记得补上这个边界。再补一个我自己经常用的排查技巧小数据对照法。写筛法的时候先用 n50 跑一遍把结果和手动列出的素数表2、3、5、7、11、13、17、19、23、29、31、37、41、43、47比一比。如果你用的是线性筛还可以故意在纸上手动推 i 从 2 到 10 的每一步标记过程跟代码输出对照。这招排查 bug 比盯代码快十倍。写到这里三种求素数的方法就全部讲完了。我自己现在的习惯是写简单测试脚本用埃氏筛反正就几行写竞赛代码或者需要配合质因数分解的题目直接上线性筛再顺手把最小质因子数组带上后面想怎么用都方便。最后再分享一个小技巧线性筛筛出来的primes数组本身就是一张天然的质数表很多题目会问“某个范围内有多少个素数”这时候直接在这个数组上做二分查找比现场再写一遍判断函数要快得多也算是把筛法的价值压榨到极致了。