洛谷P5736质数筛：试除法、埃氏筛与欧拉筛的对比与实现

1. 一道入门题，为什么会跟“筛法”绑定在一起

1.1 题面在考什么：函数封装才是这题的“正餐”

先说结论：P5736是洛谷“深入浅出”系列第七章的例题，这一章的主题是函数与结构体。所以这题表面上在考“怎么判断质数”，实际上章节的教学目标是把判断逻辑写成一个干净的函数，用传参的方式去处理每一个输入值。很多人第一次做这题时，直接在main函数里套两层循环，边读边判断边输出，代码写得又长又乱，虽然能过，但完全没有领会这一章的用意。

题面本身不复杂：输入一个n，再给n个整数，把其中所有的质数按顺序输出，空格分隔。数据范围有两个，第一行n不超过100，第二行每个数字不超过10^9。这个范围设计得很讲究——10^9这个量级，恰好卡在“暴力能不能过”的临界点上，也是很多初学者第一次感受到“算法选择”的地方。

1.2 数据范围是选算法的关键：暴力能不能过

我们先算一笔账。单个数字最大10^9，试除法判断一个数是不是质数，最坏情况要从2试到√10^9，也就是大约31623次。100个数全部判断，大约316万次运算。

这个数字是什么概念？现代CPU每秒能轻松跑上亿次简单运算，316万次在C++里连零点零几秒都用不到。所以直接用试除法交上去，AC没有任何问题。这就是为什么很多题解区的人说“我这题用暴力也过了”。

那为什么题目还要叫“质数筛”？

因为洛谷的题目编排是有教学意图的。你暴力过了，不代表你学到了筛法；下一次遇到n变成10^6，每个数还是10^9，试除法就变成了10^9次运算，虽然还能扛；再下一次遇到让你“筛出2到10^7之间所有质数”的题，比如P3383【模板】线性筛素数，试除法直接超时超到怀疑人生。P5736的定位就是给你一个“还不需要筛法也能过”的温和场景，让你在完全没有性能压力的情况下，先把筛法的逻辑学明白。等数据范围变大时，你已经有了武器。

1.3 一句话总结这题的策略

AC保底用试除法，学习目标用埃氏筛，进阶装可以用欧拉筛。我建议第一次做这题的人，三种方法各写一遍，分别提交，亲眼看看时间和内存消耗的差异。这篇文章后面会把这三种方法全部拆开讲，包括代码背后的原理、容易踩的坑，以及洛谷提交时的一些真实经验。

2. 先把手写质数判断写对：试除法的边界细节

2.1 最不容易出错的试除写法

判断一个正整数x是不是质数，教科书定义是：大于1的自然数中，除了1和它本身以外不再有其他因数。按照这个定义写出来的第一版通常是：

bool isPrime(int x) { if (x < 2) return false; for (int i = 2; i < x; i++) { if (x % i == 0) return false; } return true; }

这个代码是对的，但在x比较大的时候做了很多无用功。一个x如果不是质数，那它一定有一个因数小于等于√x。比如数字97，你从2试到96，在试到2、3、5、7时全都不能整除，其实到√97≈9.8，也就是试到9就足够了。所以优化版本是把循环条件改成i * i <= x：

bool isPrime(int x) { if (x < 2) return false; for (int i = 2; i * i <= x; i++) { if (x % i == 0) return false; } return true; }

注意两个细节：x < 2的判断必须放在最前面，因为1不是质数，0和负数也不是；另外i * i <= x在x是int类型时，当x接近int上限时i*i会溢出，所以更稳妥的写法是i <= x / i，既避免溢出，又比开平方函数sqrt(x)快得多，还不会引入浮点数精度问题。

2.2 i*i溢出问题，虽然本题不会踩但迟早会踩

本题x最大10^9，i*i最大也就10^9，不会超过int上限约21.47亿，所以用i * i写成没问题。但如果你遇到的数据范围是10^12甚至更大，比如有些题目要求判断64位整数范围内的质数，i*i一旦超过int上限就会变成一个负数或一个奇怪的小数，循环条件瞬间失效，轻则多跑很多次，重则死循环或误判。

我见过不少新手在做到“判断long long范围内的质数”时，把函数签名改成long long x，循环条件却还写着for (long long i = 2; i * i <= x; i++)，这在多数时候是安全的，因为long long能装下更大范围的平方，但补一句：当x接近9.22×10^18时，i*i同样会溢出long long。所以最保险的写法永远是：

for (long long i = 2; i <= x / i; i++)

这种写法从底层运算上就杜绝了乘法溢出的可能性。建议从一开始就养成这个习惯，省得后面还要回头改。

2.3 题目要求用函数，就按题目要求来

这道题在“函数与结构体”章节里，主函数里写一堆逻辑虽然也能AC，但编码习惯不好。正确的写法是拆成两层：main函数负责读入和输出，isPrime函数负责判断。这也是实际工程里的通用思路——一个函数只做一件事。代码组织清晰了，调试时定位问题也容易。

#include <iostream> using namespace std; bool isPrime(int x) { if (x < 2) return false; for (int i = 2; i <= x / i; i++) { if (x % i == 0) return false; } return true; } int main() { int n, a; cin >> n; bool first = true; for (int i = 0; i < n; i++) { cin >> a; if (isPrime(a)) { if (!first) cout << ' '; cout << a; first = false; } } cout << endl; return 0; }

这段代码里用了first标记来控制空格输出，保证输出结果末尾不会多出一个空格。控制空格这件事虽小，但很多面向过程输出的题目都对格式有严格要求，养成从第一道题就开始处理空格和换行的习惯，后面会省事很多。

3. 埃氏筛：第一次真正体会“筛”字

3.1 筛法的核心思想

试除法是一个一个地问“你是质数吗”，每次都要从头开始试除，费时费力。埃拉托斯特尼筛法（简称埃氏筛）换了个角度，它不判断单个数，而是直接把一个区间里的合数全部标记出来，剩下没被标记的就是质数。

具体做法：准备一个布尔数组isPrime，初始全部为true，先把0和1标成false。然后从2开始，如果当前数字i是true，说明它是质数，就把i的2倍、3倍、4倍……全部标成false。处理完i之后继续往后找下一个未被标记的数。

这个过程很像用一个筛子，把2的倍数筛掉，再筛3的倍数，再筛5的倍数……剩下那些怎么都筛不掉的，就是质数。数组里存的true和false就成了最终的质数表。

3.2 完整实现和关键行解读

#include <iostream> using namespace std; const int MAXN = 100000001; bool isPrime[MAXN]; void sieve(int n) { for (int i = 0; i <= n; i++) isPrime[i] = true; isPrime[0] = isPrime[1] = false; for (int i = 2; i <= n / i; i++) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } } int main() { int n, a; cin >> n; sieve(100000000); for (int i = 0; i < n; i++) { cin >> a; if (isPrime[a]) cout << a << ' '; } return 0; }

这里有几个关键点：

第一，外层循环只需要到√n。为什么？因为任何一个合数m，必然存在一个小于等于√m的因子。如果m是一个不大于n的合数，那么它一定会在某个i <= √m <= √n处被它的那个小因子筛掉。如果外层循环跑完了√n还没被筛掉，说明它不存在小于等于√n的因子，只能是质数。

第二，内层循环从i * i开始，而不是从2i开始。以i=5为例，2*5=10这个数在i=2时已经被筛过了，3*5=15在i=3时被筛过，4*5=20在i=2时被筛过。这些比i*i小的倍数，一定包含一个比i小的质因子，早就被更早的循环标记过了，没必要再筛一遍。从i*i开始能少做很多重复标记，虽然时间复杂度不变，但常数更优。

第三，题目中单个数字最大10^9，所以这里的isPrime数组要开到10^9+1吗？不需要，因为本题其实更适合试除法。埃氏筛在本题的正确打开方式是只筛到输入数据中的最大值。读入时记录最大值maxVal，再sieve(maxVal)，数组开成maxVal + 1大小，能省多少算多少。上面代码里我故意写了个10^8的常量，是为了说明数组尺寸和内存的关系——10^8个bool大约占100MB，很多OJ限制内存128MB，所以开10^8勉强能过；如果开到10^9，直接1GB内存，必炸。这就是为什么埃氏筛处理不了10^9级别的区间。

3.3 两个容易翻车的地方

第一个坑：数组初始化。如果你用bool isPrime[MAXN] = {false}，再想通过一个循环把所有元素改成true，没问题，但千万别忘了isPrime[0] = isPrime[1] = false。有人写了循环初始化就把0和1忘了，结果输出里混进1，WA了还在那查半天。

第二个坑：内层循环边界。写成for (int j = i * i; j <= n; j += i)，有个隐藏风险是i*i在i比较大时可能溢出int。在本题数据范围下不会，但写成long long j = (long long)i * i更保险。或者干脆用for (int j = i + i; j <= n; j += i)，放弃那个小小的常数优化，换取绝对安全。

3.4 为什么埃氏筛是 O(n log log n)

简单推导一下：对于每个质数p，需要标记n/p个倍数。所以总操作数是n/2 + n/3 + n/5 + n/7 + ...，也就是n乘以所有不超过n的质数的倒数之和。这个和约等于log log n。所以总复杂度是O(n log log n)。

log log n增长极其缓慢。n等于10^6时，log log n大约只有2.6；n等于10^8时，大约3.7。因此埃氏筛在实际运行中几乎可以当成线性看待。这也是为什么很多入门教程敢说“埃氏筛已经完全够用”，它的性能对大多数场景确实绰绰有余。

4. 想更进一步就学欧拉筛：每个合数只筛一次

4.1 埃氏筛哪里浪费了

埃氏筛虽然快，但有个不完美的地方：同一个合数会被多个质因子重复筛掉。比如30，i=2时筛一次，i=3时又筛一次，i=5时再筛一次。合数越大，质因子越多，被重复标记的次数就越多。虽然log log n的常数很小，但当n达到10^7甚至10^8时，这些无意义的重复标记会白白消耗不少时间。

欧拉筛（也叫线性筛）解决了这个问题，它的核心思想是：每个合数只被它的最小质因子筛掉一次。

4.2 欧拉筛的代码，加一行 break 就线性

#include <iostream> #include <vector> using namespace std; const int MAXN = 100000001; vector<int> primes; bool isPrime[MAXN]; void linearSieve(int n) { for (int i = 0; i <= n; i++) isPrime[i] = true; isPrime[0] = isPrime[1] = false; for (int i = 2; i <= n; i++) { if (isPrime[i]) { primes.push_back(i); } for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) { isPrime[i * primes[j]] = false; if (i % primes[j] == 0) break; } } }

这段代码的精华在if (i % primes[j] == 0) break;这一行。如果不理解它，欧拉筛就是一段背下来但随时会写错的“咒语”；理解了它，以后再写就不会错。

我们来推演一下：当i能被primes[j]整除时，说明primes[j]是i的最小质因子（因为primes是从小到大排列的质数表，能整除i的第一个质数就是i的最小质因子）。此时如果用下一个质数primes[j+1]去乘i，得到的合数i * primes[j+1]的最小质因子仍然是primes[j]，而不是primes[j+1]。这个合数应该等到i变大的某个时刻，由primes[j]作为筛除因子被处理，而不应该现在由primes[j+1]抢先筛掉，否则以后又会重复标记。所以在这里break掉，保证每个合数只被它的最小质因子筛掉一次，总操作数为O(n)。

用一个具体例子走一遍：i=6时，primes里已经有2、3、5。用2去筛，6*2=12被标为false，此时6 % 2 == 0，break。如果不break，继续用3去筛6*3=18，但18的最小质因子是2，它应该在i=9时由2*9=18被筛掉。现在筛了，后面i=9时还会再筛一次，就重复了。

4.3 选埃氏筛还是欧拉筛

对大部分竞赛题，这两种筛法都能过，但实际使用时有各自的场景。这张表是我个人做题时的心得：

如果你是刚开始学筛法，我建议先熟练埃氏筛，把它变成肌肉记忆。等做到需要用最小质因子分解质因数、求欧拉函数前缀和这类题目时，再上欧拉筛。直接跳过埃氏筛学欧拉筛也可以，但前提是你真的理解那行break的含义，而不是背模板。

对于本题P5736，n最大只有100，哪怕输入的数字是10^9，用欧拉筛筛到10^9也完全不现实。所以本题的最佳实践就是：读入时找到最大值，用埃氏筛筛到最大值，再逐个判断输出。或者干脆用第一节的试除法，代码更短。欧拉筛在这里只是为了让你提前接触，不是为了AC。

5. 洛谷提交的硬经验：从空格输出到平台抽风

5.1 输出格式：空格和换行的小习惯

洛谷的评测机对格式的判断有自己的一套逻辑：它会把你的输出和标准答案逐字符比对，但忽略行末多余的空格和文件末尾多余的换行。也就是说，多输出一个行尾空格，通常不会判WA，而是照常AC。那为什么我还要强调控制空格？因为不是所有OJ都这么宽容，有些OJ会严格比对，比如一些学校的在线评测系统，行尾空格就可能导致Presentation Error。与其每次换一个平台就踩一次雷，不如从一开始就写规范的输出。

一个比较通用的控制空格的写法是：

bool first = true; for (int i = 0; i < n; i++) { if (isPrime(a)) { if (first) { cout << a; first = false; } else { cout << ' ' << a; } } }

这种写法在判断和输出逻辑耦合的场景下用起来比较顺手。如果想要更高级一点，可以先把结果存进vector<int> res，最后统一输出：

for (int i = 0; i < res.size(); i++) { if (i) cout << ' '; cout << res[i]; }

第二种写法的好处是，判断逻辑和输出逻辑完全分离，后续想改成每行输出固定个数、或者输出到文件，都很方便。

5.2 “无法解析路由对象”这类平台异常的处理思路

洛谷的热搜词里经常出现“the route object cannot be resolved”“洛谷提交显示提交失败无法解析路由对象”这类表述。这不是代码问题，而是平台自身的偶发异常，通常由网络波动、CDN缓存、服务端部署更新等原因引起。

我第一次遇到时也慌了一下，以为是账号或者代码出问题了，后来试了几种方法，总结下来比较有效的排查顺序如下：

还有一个小经验：如果你在洛谷社区里搜问题，发现很多人都在同一天反馈同样的问题，那大概率是平台方的问题，不是你个体的原因。这时候最省心的做法就是等一段时间，而不是反复重试，反复重试还可能触发平台的提交频率限制，造成额外的“提交过于频繁”提示。

5.3 用这几道题巩固筛法

做完P5736之后，如果你想趁热打铁把筛法彻底吃透，我推荐按这个顺序刷：

• P3383【模板】线性筛素数：模板题，数据范围10^8，埃氏筛能过但欧拉筛更标准。这道题会强制你写出一个高效的筛法，因为10^8的数组和循环对常数很敏感。
• P1075质因数分解：输入一个合数，求它的最大质因数。这题用到“一个合数的最小质因子不超过√n”的性质，用试除法也能过，但配合筛法预处理可以做得更优雅。
• P3912素数个数：数据范围同样是10^8，但是求的是个数，所以数组可以用bitset或vector<bool>来压缩内存。做这题时你会真正体会到内存优化的必要性——10^8个bool要100MB，可能踩线；但bitset只占12.5MB。

我自己刷P3912时，一开始用bool数组直接开，结果MLE，后来换成bitset就过了。这个经历让我记住了“内存和时间的权衡”在实际题目里是真的会遇到的，不是书本上的空泛概念。

最后分享一点我自己的做题体会

说起来有点不好意思，我当年第一次做P5736，用的是最原始的试除法，当时还不知道什么叫“筛”。AC了，还很兴奋，觉得自己已经会了。直到后面做P3383被一个10^8的数据范围卡到怀疑人生，才老老实实回来补筛法。

回头再看，P5736这题最大的价值不是让你AC，而是让你在“暴力还能过”的时候提前接触到筛法的思路。我一直觉得刷题最重要的是“在正确的时间学到正确的东西”——如果这题的数据范围变成10^8，你被迫去学筛法，那叫“被题目教育了”；如果这题数据范围只有100，你还是主动去学筛法，那就叫“主动成长”。在做题这件事上，我建议你多当后者。