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

在求解所有不大于 $ n $ 的素数时，线性筛法（欧拉筛）都应当优先于埃氏筛法使用，因为线性筛法的时间复杂度为 $ O(n) $，低于埃氏筛法的 $ O(n \log \log n) $。

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

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

【考点】线性筛法｜埃氏筛法｜时间复杂度常数项

1. 🎯 考纲定位 GESP五级算法模块重点考查算法复杂度分析。命题人埋下这道题，就是要卡住"只记复杂度公式、不懂常数项影响"的选手——线性筛虽渐近 O(n)，但常数因子巨大，小范围数据反而比埃氏筛慢。

2. 🧠 解题思维 看到"应当优先于"就要警惕绝对化表述。线性筛确实时间复杂度更优，但代码复杂度高、常数项大；n 较小时埃氏筛因常数小、实现简单反而更快。正确做法是结合数据范围判断，不能仅凭渐近复杂度下结论。

3. 🪤 陷阱拆解 错误选项 A 的设计逻辑是让学生误以为"复杂度低=永远快"，忽略了常数项差异。最阴险的细节是"都应当优先于"——把相对优势说成绝对优势，属于典型的偷换概念。如果你只背结论而不理解本质，就会掉进这个坑。

4. 🔄 反命题思维 如果把"都"改成"当 n 足够大时"，答案就变成正确了。刷到类似题时，先问自己"命题人想考我什么"——是考复杂度符号，还是考实际效率权衡。