GESP 五级 · GESP 202309 C++ 五级 第 18 题

找出自然数 $ N $ 以内的所有质数，常用算法有埃氏筛法和线性筛法，其中埃氏筛法效率更高。

别被‘常用’二字带偏了，直接上时间复杂度：埃氏筛O(n log log n)，线性筛O(n)，线性筛更快。

很多考生看到‘常用’就下意识觉得埃氏筛更普及所以效率更高，或者只记结论不记推导，把两种筛法的复杂度记反了。其实‘常用’只是说它经典、实现简单，不代表快；线性筛虽然代码稍长，但每个合数只被最小质因子筛一次，常数更小。

【考点】算法效率与优化｜时间复杂度分析｜筛法原理

1. 考纲定位 本题考查GESP五级「算法效率与优化」模块，直接卡住考生对两种筛法时间复杂度本质的认知。命题人故意用"埃氏筛法效率更高"这个看似常识的表述，测试考生是否真正理解算法复杂度而非仅凭经验记忆。

2. 解题思维 看到题先回忆两种筛法原理：埃氏筛通过标记倍数筛除，线性筛确保每个合数仅被最小质因子筛一次。线性筛时间复杂度O(n)，埃氏筛O(n log log n)，显然线性筛更优。命题人设置这个判断题，就是要看考生能否区分"常用"与"最优"。

3. 陷阱拆解 选项A利用"常用≠高效"的思维误区，命题人偷换概念，将「埃氏筛法是经典筛法」伪装成「埃氏筛法效率更高」。最阴险的细节是题干「常用算法有埃氏筛法和线性筛法」中的「常用」二字——暗示前者更普及，诱导考生误以为普及度等同于效率。如果你只背结论而不理解本质，就会掉进这个陷阱。

4. 反命题思维 如果把「埃氏筛法效率更高」改成「埃氏筛法空间复杂度更低」，答案就变成A了。刷到类似题时，先问自己：命题人想考我什么——是时间复杂度、空间复杂度，还是算法适用场景？

5. 考频趋势 质数与合数在题库共考过52题，2024年高达21题，2025年13题，2023年7题，呈现明显上升趋势；算法类题目共7题，2023-2025年每年都有1-2题，说明算法复杂度对比是近年高频考点。

6. 预测 基于2024-2025年质数与算法类题目激增的趋势，未来GESP五级、六级乃至七级仍大概率会考查筛法复杂度对比或类似算法优化题，尤其是将“常用”“经典”等词汇与效率挂钩的陷阱题。暂无足够依据预测具体年份或题型变化，但建议持续复习两种筛法的原理与复杂度推导。