GESP 五级 · GESP 202412 C++ 五级 第 17 题

线性筛相对于埃拉托斯特尼筛法，每个合数只会被它的最小质因数筛去一次，因此效率更高。

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

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

【考点】欧拉筛｜埃氏筛｜素数

1. 🎯 考纲定位

GESP V 级数论模块，命题人卡住学生对两种筛法的本质区别认知——多数考生混淆"标记次数"与"效率"，误以为埃氏筛也满足每个合数仅被筛一次。