GESP C五级的知识点里埃氏筛和线性筛是公认的“第一次让你真正感受到算法效率”的内容。很多同学刚学到这里都会有个共同的困惑代码看起来差不多名字又很像到底学哪个考试默写哪个为什么明明暴力也能判断质数非要搞出这么两个筛法来这篇我就把这两个筛法的来龙去脉一次讲透包括它们各自解决什么问题、代码里的每个边界是怎么来的、考场上怎么选怎么写以及我这些年在实际教学和做题中见过的高频丢分点。打算备考五级、或者刚接触筛法想真正弄明白原理的人都可以按这个顺序往下看。1. 五级真正想考你的是什么看懂筛法在大纲里的位置1.1 从单个质数判断到批量质数输出在学筛法之前所有人判断质数用的都是同一种办法试除。拿2到sqrt(x)挨个试看x能不能被整除。这个思路本身没错但它的效率上限非常低。GESP五级这个阶段算法要求已经从“能跑出结果”上升到了“在限制时间内跑出结果”而“批量判断素数”就是这个要求最典型的载体。假如要统计1到n之间有多少个素数用暴力法对每个数单独试除总复杂度是O(n sqrt(n))。很多同学第一次意识到这个复杂度会愣一下n10^5的时候sqrt(n)大概是316乘起来就是三千多万次取模运算运气好勉强能跑n一旦到10^6那就是十亿次量级的运算基本可以宣告超时。换句话说单个判断素数的方法并没有错错在把它套用到批量场景下反复使用。这时候就需要换个思路能不能一次性把1到n所有数的素数/合数状态全部算出来埃氏筛和线性筛解决的都是同一个问题区别只在于效率不同。它们本质上不是更高级的判断法而是更高明的预处理法。你花一次预处理的代价换来一张可以反复查询的“素数状态表”之后不管题目问多少次、怎么组合着问都能快速响应。这个“预处理查询”的思路比筛法本身更值得先刻在脑子里。1.2 筛法背后的“状态标记”思维我见过太多人上来就背代码背完就忘原因就是没有抓住筛法的本质。筛法的本质特别朴素用一个数组记录每个数的状态然后用循环批量改写这些状态。你可能会觉得这没什么了不起但“状态数组批量更新边界控制”这个组合是后面一大片算法技巧的地基。前缀和是这个套路差分是这个套路很多动态规划的初始化和状态转移也是这个套路。你在筛法这里把“预处理”“状态标记”“循环边界”这三件事真正弄懂了后面学什么都会顺畅很多。另外虽然标题写着“语法知识”但埃氏筛和线性筛真正用到的语法点其实少得可怜一个bool数组、两个for循环、一个if判断线性筛再加一个vector而已。它更像是在一个简单的语法框架里考你能不能把思路转化成没有越界、没有漏数的代码。2. 埃氏筛最符合直觉的批量筛法2.1 暴力试除的问题到底出在哪我想先让你直观感受一下暴力的瓶颈。如果只用试除法统计1到10^5的素数个数大约要做三千多万次取模实际跑起来零点几秒还能接受。但数据量一旦升到10^6十亿次取模时间就奔着秒级去了。到了10^7暴力基本就告别考场了。暴力法最大的问题不是某一次判断慢而是每次判断都在重复劳动。判断17是不是素数你要试2、3、4直到sqrt(17)全不整除得出结论然后判断19又要重新从2开始试一遍。每个数都是一场独立的“盘问”前面判断出的信息完全被浪费掉了。但素数这个概念本身是有传播性的只要确认了一个数是素数那它的所有倍数就都是合数反过来任何一个合数都必然能写成某个更小素数的倍数。把这个传播性利用起来就是埃氏筛的核心思想。2.2 点名思想与两个让埃氏筛变快的优化埃氏筛的做法可以理解成一个点名过程从2开始。2没有被标记过所以它是素数。然后让所有2的倍数“出列”标记成合数。接着看3。3没有被标记过是素数把3的所有倍数标记为合数。4已经被2标记过了跳过。5没被标记过是素数标记所有5的倍数。一路扫到n。任何一个合数比如77 7 × 11它在枚举到因子7的时候一定会被标记。所以当外层循环全部走完还没被标记的那些数就是素数。埃氏筛有两个关键优化理解了这两个优化代码才能写得干净又不出错。第一个优化内层从 ii 开始标记而不是从 2i 开始。原因是 i 的 2 倍、3 倍这些数它们的质因子比 i 小早就被更小的素数标记过了。比如筛5的倍数时10、15、20早就被2或者3标掉了25才是第一个需要“5亲自出马”的数。第二个优化外层循环只需要跑到 sqrt(n)。如果 x 是一个合数那它一定有一个因子 d 不超过 sqrt(x)也就是说在枚举到 d 的质因子时x 就已经被标记掉了。所以 i 超过 sqrt(n) 之后剩下还没被标记的数不可能再被更大的 i 标记它们就是纯纯的素数。参考实现如下。这里我用 vis 数组统一记录“是否是合数”而不是用一个 isPrime 数组因为这样语义统一后面学线性筛的时候也更好衔接#include bits/stdc.h using namespace std; const int MAXN 1000005; bool vis[MAXN]; void eratosthenes(int n) { for (int i 2; 1LL * i * i n; i) { if (!vis[i]) { for (long long j 1LL * i * i; j n; j i) { vis[j] true; } } } }筛完之后vis[x]为false就代表x是素数。这里有个很常见的坑vis[1]默认是false但1既不是素数也不是合数所以遇到需要查1的场景要提前把vis[1]置为true否则会把1当成素数。2.3 复杂度为什么是O(n log log n)埃氏筛的总操作次数是所有素数 i 对应的 n/i 求和也就是 n/2 n/3 n/5 n/7 …。提取公因子 n 之后括号里是“全体素数的倒数和”。数论里有一个结论不超过 n 的素数倒数之和大约是 log log n 加上一个小常数。因此总复杂度是 O(n log log n)。这个式子看着抽象算一下就直观了。n1000000 时log log n 大约是2.6所以整个筛法实际做的标记操作是百万量级跟暴力的十亿次取模直接差了三个数量级。我第一次在评测机上跑 1e6 的埃氏筛看到答案瞬间出来对比之前暴力版要等上好几秒才算真正理解了“数据规模决定算法思路”这句话。实测体感上埃氏筛在 n10^6 这个量级非常轻松到 n10^7 才开始有时间压力。这个体感数据在后面选型的时候很有用先记着。3. 线性筛把常数的水分也挤干3.1 埃氏筛什么时候会重复筛埃氏筛有一个小遗憾同一个合数可能被多个质数重复标记。比如30先被2标记一次2×15又被3标记一次3×10还会被5标记一次5×6。一个数被标三次中间至少有两次是白干的。n越大这种重复标记的总量越可观虽然复杂度还是O(n log log n)但常数确实不够优雅。线性筛要做的事情就一件让每个合数只被标记一次。那到底该由谁来标记它答案藏在一个朴素的原则里由它的最小质因子来标记。这是线性筛的灵魂后面所有代码设计都是在为这一句话服务。3.2 最小质因子原则与核心代码线性筛代码很短但很多人背不下来原因是没真正理解那几行的作用。先看标准写法#include bits/stdc.h using namespace std; const int MAXN 1000005; bool vis[MAXN]; vectorint primes; void linearSieve(int n) { for (int i 2; i n; i) { if (!vis[i]) { primes.push_back(i); } for (int j 0; j (int)primes.size(); j) { long long v 1LL * i * primes[j]; if (v n) break; vis[v] true; if (i % primes[j] 0) break; } } }流程是这样的从小到大枚举 i如果 i 没被标记过就说明它是素数加入质数表然后拿质数表里已有的每个质数 p 去乘 i把乘积 p*i 标记为合数当 i 能被 p 整除时立刻停止内层循环。为什么说每个合数只会被标记一次看任意合数 x它一定有一个最小质因子 p。把 x 写成 p × m其中 m x / p。因为 p 是 x 的最小质因子所以 m 里面不可能含有比 p 更小的质因子。当我们循环到 i m 的时候质数表从小到大枚举在碰到 p 之前绝不会触发 break于是会顺利走到 p 这一步把 p × m x 标记掉。这个标记动作完成后是否break取决于 m 是否能被 p 整除但核心问题是x 唯一的标记机会就在 i m、质数 最小质因子这一组合上别的时候都到不了这一步。所以线性筛真正做到了“不重不漏”。3.3 break那一行决定了线性的性质我改卷时见过不少同学把代码背反了先写 if (i % primes[j] 0) break再写 vis[v] true。这个顺序错了会出大事。如果先break当 i 能被 p 整除时p*i 这个数就永远不会被标记而它恰恰应该由 p 来标记结果就是整个筛法漏数。所以顺序必须先把 vis[v] 置为true再去判断是否break。break条件为什么是 i % p 0因为这时 p 已经是 i 的最小质因子了。一个合数 pi 的最小质因子等于 min(p, i 的最小质因子)。当 p 小于 i 的最小质因子时乘积的最小质因子就是 p由 p 标记它是合理的一旦 p 超过了 i 的最小质因子乘积的最小质因子就变成 i 里的那个更小的因子而不是 p。此时如果不break用更大的 p 去标记 pi就等于是用它“不该标记”的数以后这个数还会被它真正的最小质因子再标记一次线性就变成非线性了。举个例子帮助固化理解。i 6 的时候质数表里是 [2,3,5]。先取 p2v12标记12然后因为 6%20 直接break。如果不break下一步 p3 就会标记18。但18 2 × 9最小质因子是2它应该由 i9、p2 的时候标记让3提前标记了18之后18还会被2再标记一次。所以那个break不是性能上的小优化而是正确性里的一环。3.4 手工走一遍流程加深理解我把前几轮循环的实际情况列出来你最好拿笔跟着推一遍i2vis[2]为falseprimes变成[2]。内层 p2标记42%20停止。i33未标记primes变成[2,3]。p2标记63%2!0继续p3标记93%30停止。i44已标记primes不变。p2标记84%20停止。i55未标记primes变成[2,3,5]。p2标记10p3标记15p5标记255%50停止。i6已标记。p2标记126%20停止。你看6在i3时被标记9在i3时被标记12在i6时被标记15在i5时被标记而18会在后面i9、p2那一次被标记。每个合数都正好被它的最小质因子照顾到一次不多不少。手动走个十几轮比背十遍代码都管用。4. 两个筛法怎么选复杂度之外还要看这些4.1 从复杂度到常数的对比先说结论在五级考场上很多题用埃氏筛和线性筛都能过选哪个更多取决于题目类型而不是“哪个更快”。理论上线性筛复杂度是O(n)埃氏筛是O(n log log n)后者更好看但实际上当n10^6的时候两个筛子的运行时间几乎看不出差别都接近瞬间完成。n到了10^7差距依然在同一个数量级内真正影响体感的是常数和代码稳定性而不是那个log log n。我习惯用的对比表是这样的对比项埃氏筛线性筛时间复杂度O(n log log n)O(n)代码难度简单不需要维护质数表稍复杂要理解break什么时候触发重复标记有但常数可接受无最小质因子不能直接得到顺手就能维护扩展能力弱强可以延伸到欧拉函数等积性函数考场出错风险低中break顺序和位置容易错从这个表能看出来单纯为了“找素数”这个需求埃氏筛其实是性价比之王代码短、出错率低、思维负担小。线性筛真正的价值更多体现在扩展性上。如果你后面要做质因数分解、求欧拉函数、求莫比乌斯函数线性筛的框架能直接复用埃氏筛想扩展就没那么顺手了。4.2 场景选型什么时候不值得写线性筛我自己判断用什么筛子标准很简单只输出1到n的素数个数或者判断若干个数是否为素数n不超过10^7直接用埃氏筛别犹豫。代码少心态稳。题目要求每个数的最小质因子、频繁做质因数分解、或者牵扯到积性函数用线性筛因为框架天然支持。如果n非常大但只查一个很小的区间两个筛法都用不上那是区间筛和素数判定算法的领域五级暂时不会考到这个深度。还有一个容易被忽略的点线性筛虽然每个点只标记一次但它的内存访问是跳跃式的要用质数表去乘当前的i埃氏筛则是连续地跳着标记倍数。两种访问模式在真实硬件上的表现并没有压倒性差异。所以考场上真正要担心的不是“我选了埃氏筛会不会常数过大”而是“break写没写对、边界有没有越界”。4.3 内存优化与功能扩展考场上开10^7的bool数组占用10MB完全没压力。但如果你用int数组存“是否是合数”同样10^7就是40MB部分评测机会开始告警。所以vis数组一定要用bool或者char没必要用int去装。想要顺手得到最小质因子在线性筛的标记处加一行就行vectorint primes; int lp[MAXN]; // 最小质因子 void linearSieve(int n) { for (int i 2; i n; i) { if (!lp[i]) { lp[i] i; primes.push_back(i); } for (int j 0; j (int)primes.size(); j) { long long v 1LL * i * primes[j]; if (v n) break; lp[v] primes[j]; if (i % primes[j] 0) break; } } }这个lp数组做质因数分解特别顺手每次取p lp[x]x / p重复到x变成1就能把质因子按从小到大全部提出来。后期如果做“分解质因数计数”这类综合题这玩意儿是神器。5. 五级考场上的出题姿势与默写模板5.1 四种绕不开的考法第一种直接数个数。给一个n输出1到n之间有多少个素数。筛完之后遍历vis统计就行难不难的不在于筛法而在于看清“包不包括n”这个边界很多人死在这里。第二种多轮询问。给m个数每个都问是不是素数。如果对每个数单独试除m一大就扛不住。正确做法是先筛到题目允许的最大上限之后每次询问直接O(1)查vis数组。这类题考的就是“预处理查询”的意识。第三种区间统计。给[l, r]问区间内素数个数。做法是筛完后做前缀和sum[i] sum[i-1] 当前数是否为素数区间答案就是sum[r] - sum[l-1]。这个组合在五级题目里很常见相当于把两个基础技巧拼在一起。第四种质因数分解。配合前面那个lp数组循环用最小质因子去拆。输出时要考虑特判输入为1、输入本身就是质数。这两类特判虽然简单但最容易漏。5.2 按出现频率排名的易错点结合我自己的比赛经历和给同学改题的经验筛法题丢分的位置高度集中忘记处理1。默认vis[1]false会把1当成素数筛完要单独排除1或者在建数组时直接vis[1]true。埃氏筛内层从2i开始而不是从ii开始。后果只是变慢不会错但在n较大的时候容易判超时。ii溢出int。i是int时i超过46340左右ii就爆了。习惯写成1LLii或者in/i养成习惯之后每次都不慌。线性筛先break再标记。这个顺序错了在n较小时可能只漏一两个数样例一过就交丢分丢得莫名其妙。数组开小一位。很多同学开数组时用了MAXN但循环跑到了n下标正好越界。保险起见数组一律开成MAXN5。5.3 一份低出错率的考场模板我备考时给自己定过一个默写顺序如果时间够直接写线性筛因为它内部已经包含质数表的生成多数质数相关题都能套如果时间紧就退一步写埃氏筛代码更短更不容易写错。下面这套是我自己在练习中打磨过的模板区间素数个数的考法可以直接拿去用#include bits/stdc.h using namespace std; const int MAXN 1000005; bool vis[MAXN]; int primeCnt[MAXN]; vectorint primes; void buildSieve(int n) { vis[1] true; for (int i 2; i n; i) { if (!vis[i]) { primes.push_back(i); } for (int j 0; j (int)primes.size(); j) { long long v 1LL * i * primes[j]; if (v n) break; vis[v] true; if (i % primes[j] 0) break; } } for (int i 1; i n; i) { primeCnt[i] primeCnt[i - 1] (!vis[i]); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin n q; buildSieve(n); while (q--) { int l, r; cin l r; cout primeCnt[r] - primeCnt[l - 1] \n; } return 0; }这个模板开头直接把vis[1]置为trueprimeCnt自然就不会把1算成素数了。5.4 考前一周怎么练筛法给你一套我自己带学生用的练习路线照着走就行第一天手算。拿n20或者30不写代码用笔画标记过程把每个合数是被谁标掉的写出来。线性筛就会在纸上呈现出“每个数只被删一次”的样子这种感觉是看代码看不出来的。第二天默写。给自己十分钟合上书把线性筛完整写出来再对照上面的模板逐行检查重点看break位置有没有放错、乘法有没有用long long。第三天到第五天刷题。按前面说的四种考法各做两三题尤其注意“区间素数个数质因数分解”这种组合题把预处理思想练成条件反射。最后两天限时模拟。模拟时就把模板当最终答案不要现场改来改去。我个人觉得筛法题难的不是理解而是两个地方能不能在最紧张的时候仍然写对边界以及能不能一眼看出题目需要“预处理”而不是“反复判断”。这两点靠背模板解决不了只能靠动手走几轮。最后补一句我的习惯线性筛虽然看起来多几行但它的break逻辑让我安心所以正式比赛里我几乎总是用线性筛但如果只是自己写个小工具快速筛个素数个数我反而会切回埃氏筛因为它真的不怕写错。你自己选一个主用方案把它练到闭眼写对比两个都想抓着用要可靠得多。