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

线性筛关键是“每个合数只会被最小质因子筛到一次”，因此为 $O(n)$。

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

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

【考点】线性筛（欧拉筛）｜合数分解｜时间复杂度分析

线性筛属于《GESP 五级算法模块》"数论与筛法"核心内容，命题人放这道题，专卡只背结论的学生——他们容易把"线性筛"和"普通埃氏筛"混淆，误以为筛法复杂度必然 O(n log log n) 或 O(n)。

看到"线性筛"和"每个合数只会被最小质因子筛到一次"，应立刻想到欧拉筛机制：对每个合数 x，它一定被其最小质因子 p 筛掉，且只会被 p 筛掉一次。因此每个合数只被处理一次，总操作次数等于合数个数，即 O(n)。这一类的通法是：分析筛法中每个数被"筛掉"的次数，若次数为常数，则复杂度为 O(n)；若次数随质因数个数增长，则复杂度更高。

选项 B 的错误在于认为筛法复杂度一定高于 O(n)。命题人利用"筛法"和"线性筛"两个概念容易混淆的误区，把普通埃氏筛（O(n log log n)）的复杂度套用到线性筛上。如果只背结论，学生可能认为"筛法复杂度都是 O(n log log n)"，从而选 B。最阴险的细节是"每个合数只会被最小质因子筛到一次"——这句话直接揭示了线性筛的线性本质，但很多学生只记住了"线性筛"这个名字，没深入理解其筛法过程，因此掉进陷阱。

如果把"每个合数只会被最小质因子筛到一次"改成"每个合数只会被任意质因子筛到一次"，那么就不能保证线性复杂度，因为合数可能被多次筛掉。命题人想考的是对筛法机制的理解，而非单纯记忆。刷到类似题时，先问自己："筛法中每个数被处理几次？为什么？"