GESP 五级 · GESP 202606 C++ 五级 第 6 题

下面关于埃氏筛法的说法正确的是（ ）。

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

1不是质数也不是合数。埃氏筛法标记时从i×i开始而非从2×i开始，因为小于i×i的倍数已经被更小的质数筛过。

【考点】埃氏筛法原理｜素数判定

【考纲定位】GESP 五级核心考点，直接考察埃氏筛法原理。命题人卡住考生对"筛除过程"的理解，多数人选错因混淆了"单次筛除"与"多重筛除"的区别。

【解题思维】核心观察：埃氏筛法本质是"从每个素数出发，标记其倍数"。B 项精准描述了算法流程——对每个素数 p，将其所有倍数（2p,3p,...）标记为合数。A 项错在"只筛一次"：合数 6 会被 2 和 3 分别筛掉，实际筛除次数等于其不同素因子个数。C、D 项属于常识性错误，筛法显然能求素数表且不限于偶数。

【陷阱拆解】A 项是"单次筛除"的伪命题：合数 6 会被 2 和 3 分别筛掉，实际筛除次数等于其不同素因子个数。C 项偷换概念，筛法求素数表，绝非仅判偶数。D 项自相矛盾，筛法核心产出就是素数表。命题人利用"合数"与"素数因子"的混淆，以及"筛除次数"的直觉偏差，精准筛选出仅理解本质的考生。

【反命题思维】若改为"只筛偶数倍数"，则遗漏 3,5,7 等素数；若改为"只筛 3 的倍数"，则遗漏 2,5,7 等素数。命题人想考的是"筛除过程"的本质——每个素数都要作为起点筛除其倍数，缺一不可。