GESP 五级 · GESP 202509 C++ 五级 第 8 题

关于埃氏筛和线性筛的比较，下列说法错误的是（ ）。

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

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

【考点】埃氏筛原理｜线性筛原理｜时间复杂度与常数因子

考纲定位：GESP 五级《数论基础》模块"素数筛法"必考内容。命题人专卡"只背结论、不懂原理"的考生——把理论复杂度直接等同于实际速度，是 GESP 五级最经典的思维陷阱。

解题思维：先拆两种筛的本质。埃氏筛枚举每个素数的倍数，每个合数会被它的所有质因子各自标记一次，必然重复。线性筛维护质数表，遍历每个数时只标记其最小质因子的倍数，保证每个合数只被筛一次。因此线性筛理论复杂度 O(n) 优于埃氏筛 O(n log log n)。但理论复杂度只是指示，实际运行速度还取决于常数因子：埃氏筛实现极简无额外存储，常数极小；线性筛需维护 prime 数组和判断质因子逻辑，常数较大。所以在 n ≤ 10^7 这种常见范围，埃氏筛往往更快。

陷阱拆解：A 正确，重复标记是埃氏筛固有缺陷；C 正确，最小质因子筛是线性筛核心；D 正确，常数优势在中等规模范围明显。B 错在偷换概念——把"理论复杂度更优"直接等同于"速度往往更优"，完全忽略常数因子影响，这是命题人专设的"绝对化表述"陷阱。

反命题思维：若范围改到 n ≤ 10^9，埃氏筛会超时，线性筛虽常数大但 O(n) 仍占优，答案会反转；若改成"哪种筛法更适合内存受限场景"，埃氏筛无需存储质数表，线性筛需要，答案也会变。刷到类似题，先问"命题人想考我什么"，再对比常数与范围，别被"理论最优"蒙蔽。