GESP 五级 · GESP 202409 C++ 五级 第 17 题

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

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

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

【考点】算法复杂度分析｜埃氏筛法｜线性筛法

GESP五级明确要求掌握质数筛的两种主流实现。命题人卡住的是考生对“效率”概念的模糊认知——只背结论不分析时间复杂度，在涉及大数范围时极易误判。

看到题先想：两种筛法的时间复杂度。埃氏筛每处理一个合数会重复标记，复杂度 $O(n \log \log n)$；线性筛通过维护最小质因数表，保证每个合数只被标记一次，复杂度 $O(n)$。线性筛效率更高是算法竞赛中的经典结论，直接选A。

错误选项B的设计利用了“线性筛名字更‘线性’，所以一定更快”的直觉陷阱。若考生只背“线性筛效率高”而不理解其 $O(n)$ 的数学本质，看到“常用算法有……其中线性筛法效率更高”时容易凭印象选错。题目最阴险的细节是“常用算法”四个字——它暗示考生只需知道“有这两种”，却忽略了“效率比较”才是判断依据。

若把条件改成“找出 $10^{12}$ 以内的所有质数”，单纯比较筛法效率已不够，会转向讨论筛法结合分段存储或位压缩等优化。一句话提醒：刷到类似题时，先问自己“命题人想考我什么”——是考算法名称记忆，还是考复杂度分析能力？