GESP 五级 · GESP 五级样题（C++ 组） 第 18 题

埃氏筛法用于找出自然数 $N$ 以内的所有质数，其时间复杂度为 $O(N sqrt{N})$，因为判定一个数是否为质数的时间复杂度为 $O(N)$。（ ）

这题考的是埃氏筛法的核心原理与复杂度。拿到题先想：筛法不是对每个数做试除，而是用已找到的质数去标记倍数。题目说"判定一个数要O(N)"，这直接违背筛法思想，所以答案选B。

学生容易把筛法和逐个判定的朴素试除法搞混，误以为筛法也要对每个数做O(√N)的试除从而得到O(N√N)。还有一个细节陷阱：题目声称"判定一个数是否为质数的时间复杂度为O(N)"，这本身就不对，试除法应该是O(√N)，命题人故意用双重错误来迷惑只背结论的考生。

考点定位

GESP五级"算法基础"模块，核心考察经典筛法的时间复杂度认知。命题人卡住的是考生对"筛法≠逐个判定"的本质理解——他们混淆了埃氏筛法O(N log log N)与朴素试除法O(N√N)的数量级差异，这是五级算法思维的典型分水岭。

解题思维

思考链：看到"埃氏筛法"→回忆其核心操作是"标记倍数而非逐个试除"→对比题目声称的"判定一个数需O(N)"→发现该理由与筛法流程矛盾→判定错误。

通法：筛法类问题必须从"如何生成合数标记"入手。埃氏筛每次处理质数p时，从p²起标记p的倍数（因为更小的倍数已被更小的质数筛过），总操作量约为N(1/2+1/3+1/5+...)≈N log log N。记住：筛法的复杂度取决于合数被标记的次数，而非数的个数。

陷阱拆解

选项A的陷阱在于偷换概念：命题人故意用"判定一个数是否为质数"（O(√N)）来包装，让考生误以为是O(N√N)的朴素试除。但埃氏筛法的精髓就是避免逐个判定！

最阴险的细节："因为判定一个数是否为质数的时间复杂度为O(N)"——这句话本身就有问题。试除法的复杂度是O(√N)，不是O(N)。命题人用双重错误（筛法原理错+复杂度表述错）来迷惑只背结论的考生。

反命题思维

若把题目改为"埃氏筛法的时间复杂度为O(N log N)"，答案仍错——因为log log N与log N是数量级差异。若问"线性筛法能否在O(N)内求N以内质数个数"，则答案为是（欧拉筛）。

刷到筛法题时先自问：这题考的是筛法原理，还是单纯套公式？

考频趋势

质数与合数在题库共考过52题，覆盖7个级别；算法类仅考过7题，复杂度分析题39题。筛法作为算法核心，近年GESP五级出现频率较高，是必考内容。

暂无足够依据预测未来具体出题形式，但筛法原理与复杂度对比仍是高频考点。