GESP 五级 · GESP 202603 C++ 五级 第 24 题

线性筛相比埃氏筛的核心改进在于：埃氏筛中一个合数可能被多个质数重复标记，线性筛通过“每个合数只被其最大质因子筛去”的策略，保证每个合数恰好被标记一次，从而实现 $O(n)$ 的时间复杂度。

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

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

【考点】线性筛｜埃氏筛｜时间复杂度

【考纲定位】考纲五级“算法效率”模块，线性筛与埃氏筛对比是高频考点。命题人专攻学生“只记结论不究细节”的弱点——看似“每个合数只标记一次”完全正确，实则暗藏对“最大质因子”这一关键表述的偷换陷阱。

【解题思维】核心推理链：埃氏筛中 x·p 会被所有 p≤min(x,min_prime(x)) 重复标记；线性筛通过循环条件 i%primes[j]==0 确保每个合数仅被其最小质因子筛去。命题人故意将“最小质因子”偷换为“最大质因子”，利用考生对“唯一标记”的模糊记忆掉入语义陷阱。

【陷阱拆解】三个致命错误：1.“最大质因子”表述与线性筛构造逻辑完全相悖（实际是标记最小质因子）；2.偷换概念将“恰好一次”的标记机制简化为“最大质因子”这一无关属性；3.若按“最大质因子”理解，则 2·3=6 会被 3 标记，但 3 是 6 的最大质因子，而 6 实际应被 2 筛去，导致逻辑矛盾。命题人利用“唯一标记”这一正确结论的模糊印象，设计了一个看似合理实则完全错误的描述。

【反命题思维】若将“最大质因子”改为“最小质因子”，该命题立刻成为正确描述，这正是命题人设计的“语义陷阱”本质。刷题时遇到类似表述，先自问：这个结论是否精确？线性筛的核心价值在于“每个合数仅被最小质因子筛去”，而非“最大质因子”。记住这个精确表述，就能避开所有同类陷阱。