GESP 五级 · GESP 202406 C++ 五级 第 19 题

找出自然数 $n$ 以内的所有质数，常用算法有埃拉托斯特尼（埃氏）筛法和线性筛法，其中埃氏筛法效率更高。

埃氏筛法：从2开始标记倍数为合数，O(n log log n)。线性筛（欧拉筛）：每个合数只被最小质因子标记一次，O(n)。线性筛效率更高。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】数论基础｜筛法原理｜算法复杂度分析

🎯 考纲定位

数论与筛法属于 GESP 五级数论模块核心内容。命题人放这道题，就是要卡住那些「只背结论不推复杂度」的考生——五级考生往往对埃氏筛和线性筛的代码都背过，但很多人没真正理解两者时间复杂度的本质差异。

🧠 解题思维

看到题先想什么？筛法的两种实现机制：埃氏筛法对每个质数 p，会遍历 p 的倍数（p,2p,3p...）进行标记；线性筛法则保证每个合数只被其最小质因数筛一次。关键观察是：埃氏筛法每个合数可能被「多次标记」（如 12 会被 2、3 分别筛到），而线性筛法每个合数只被筛一次。由此推得：埃氏筛法复杂度 O(n × 1/2 + n × 1/3 + n × 1/5 + ...) = O(n log log n)；线性筛法复杂度 O(n)。题干说「埃氏筛法效率更高」，与复杂度结论相反，故选 B。

🪤 陷阱拆解

A 选项是典型「语义陷阱」——命题人利用考生对「实现简单」与「时间复杂度」的混淆。埃氏筛法代码确实更简洁（无需维护质数列表），但线性筛法在算法竞赛中是处理大数筛法的「黄金标准」。考生若只凭「背过埃氏筛快」的模糊印象，不推导复杂度，就会掉进这个陷阱。此外，题干「常用算法有...其中...效率更高」的表述方式，暗示考生需要判断的是「通常情况」而非「特定小 n 范围」，这是另一个隐蔽的边界条件提示。

🔄 反命题思维

命题人想考的不是筛法本身，而是「算法复杂度」这一核心概念。若将题干改为「哪种筛法适合处理大数」，答案不变；若改为「哪种筛法代码更短」，则选埃氏筛。刷到类似题，先问自己「命题人想考我什么」，再决定是背结论还是推导。