GESP 六级 · GESP 202403 C++ 六级 第 13 题

线性筛法与埃氏筛法相比的优势是（ ）。

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

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

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

🎯 考纲定位

GESP C++ 六级算法模块，筛法专题。命题人卡住的是"只背结论不证复杂度"的考生——多数人凭记忆选 A 或 B，却说不清为什么线性筛真的快。