企业官网建设流程全解析

洛谷P5736【深基7.例2】质数筛，题面就一句话：输入 n 个数，把里面的质数挑出来。我刚接触这道题时，觉得它简单到不需要动脑，直接每个数从2除到√x，交上去一路AC。可等我回头翻题解，看到埃氏筛、欧拉筛两种写法摆在眼前，才明白这道题真正的用心：它用一组“数量少但值很大”的数据，逼你去想筛表的边界该划在哪里，想筛法为什么比逐个试除舒服，以及什么时候筛法反而不能硬套。这些想明白了，P5736才算真正做完了。

这篇内容适合三种人：刚刷完分支循环、第一次接触质数筛的新手；会背埃氏筛但没认真推导过欧拉筛的进阶选手；以及想认真吃透一道基础题的严谨型刷题人。我会把题目数据拆开讲，再把两种筛法的原理、代码、坑点一条龙铺开，最后聊聊筛法还能往哪些方向延伸。

1. 题目拆解：P5736到底在考什么

1.1 数据范围的设计意图

先看数据范围：n≤100，每个数不超过10^9。这个组合非常有意思。如果n很大而ai很小，比如n=10^5、ai≤10^6，那题目指向很明显：直接把1到10^6的质数表筛出来，再用O(1)判断每个ai。如果n很小而ai也很小，比如ai≤100，那暴力试除就完事了，根本不用学筛法。偏偏它给的是n=100、ai≤10^9，卡在中间。

如果暴力判断每个数，单个数要试除到√(10^9)≈31623，100个数最多做316万次取模，程序眨眼就跑完了，所以单纯为了AC，暴力确实能过。但问题来了：题目名字叫“质数筛”，考察点注定是筛法。你见过哪道叫“质数筛”的题让你一个一个试除的？所以这道题的正确姿态，是先筛出一张足够大的质数表，再用这张表去判定输入的每个数。

这里就引出一个关键判断：需要筛到多大？因为ai最大是10^9，合数x一定有一个不超过√x的质因子，√(10^9)≈31623。所以只要筛出31623以内的质数，就能覆盖所有10^9以内合数的最小质因子范围。这个“筛表上限跟着判定需求走”的思想，是这题真正想教的东西，也是后面很多数论题的共同起点。

1.2 暴力试除能AC，但你真的会筛法吗

我把三条路线的复杂度拉一张表，看完你就明白出题人为什么这么设计数据：

先解释一下3400这个数字：31623以内一共有约3401个质数（π(31623)≈3401），所以用质数表试除一个10^9以内的数，最坏情况就是从头试到p*p>x为止，最多3400次取模。100个数就是34万次，比暴力的316万次少了一个数量级。

再看第三种方案：如果真的开一个bool数组标记1到10^9的合数，bool在C++里是1字节，光数组就要1GB，OJ上根本开不出来。即使用bitset压缩成1bit也要125MB，依然不安全。所以这道题不能“无脑筛到最大值”，必须筛到根号级别，再用质数表去试除。这个“筛表上限折中”的设计，才是筛法是否适用的核心分界线。

2. 埃氏筛：简单直观的合数标记法

2.1 核心思想：质数留名，合数划掉

埃氏筛全称是“埃拉托斯特尼筛法”，思路朴素到一句话就能说清：一个质数的倍数一定是合数。

从2开始遍历，如果当前数字i没被标记为合数，那它就是质数；然后把i的所有倍数标记成合数。一直做到上限，剩下的没被标记的数全是质数。

这里有一个很关键的优化：标记倍数时，不需要从2i开始，直接从i*i开始就够了。为什么？因为2i、3i、(i-1)i这些数，都已经被更小的质因数筛过了。比如i=7时，2×7=14早被2筛过，3×7=21早被3筛过，5×7=35早被5筛过，所以直接从7×7=49开始标记。这个优化能省掉大量重复工作，尤其对较大的质数。

这个思想用生活类比来说，就像开班会点名：每报到一个人，就把所有和他同宿舍的人都划掉，剩下没被划掉的就是独立宿舍。虽然划人的时候可能有人被划了好几次，但整体上效率比挨个问“你是不是独立宿舍”高得多。

2.2 代码实现与两个关键优化点

埃氏筛的代码非常短：

const int LIM = 31623; vector<int> primes; bool isComp[LIM + 1]; void eratosthenesSieve() { for (int i = 2; i <= LIM; i++) { if (!isComp[i]) { primes.push_back(i); for (long long j = 1LL * i * i; j <= LIM; j += i) { isComp[j] = true; } } } }

这段代码里有三个细节值得单独拎出来说。

第一，1LL * i * i这个写法，看起来多余，其实是在防int溢出。LIM=31623时，ii≈10^9，还没超过int上限，但万一你把LIM改成40000，ii就到16亿了，还在int范围内；改成50000，i*i就是25亿，直接溢出变成负数，后面的循环就可能死循环或者漏筛。养成写1LL * i * i的习惯，换数据范围时不会踩坑。

第二，为什么不在外层循环里把所有数的倍数都筛一遍，而是只在if (!isComp[i])成立时筛？因为如果i已经被标记为合数，说明i有更小的质因子，i的所有倍数也必然有这个质因子，早就被更小的质数标记过了，再筛一遍纯属浪费。

第三，内层循环从ii开始，这一句我前面讲过了。但注意，如果ii已经超过LIM，内层循环不会执行，但i本身依然要加入primes表。也就是说，埃氏筛的加入质数表和标记倍数，是两件可以分开做的事。

3. 欧拉筛：每个合数只被筛一次

3.1 埃氏筛的冗余在哪里

埃氏筛有个小毛病：同一个合数会被标记好多次。比如12，2的倍数会标记它，3的倍数也会标记它；再比如30，2、3、5都会标记它。虽然从整体上看，埃氏筛的时间复杂度是O(n log log n)，已经非常接近线性，但标记次数的冗余始终让人不舒服。

当筛法规模大到1e7甚至1e8时，这个冗余就明显了。欧拉筛（也叫线性筛）就是冲着“每个合数只被筛一次”去的，它能把总复杂度稳定在O(n)。

欧拉筛的思路是：每个合数只被它的最小质因子筛掉。比如12，只让质数2去筛它，不让3去筛它；30只让2去筛，不让3和5去筛。要做到这一点，就不能像埃氏筛那样一个质数一路标到底，而要在标记过程中随时“刹车”。

3.2 线性筛原理与核心break条件

看代码：

const int LIM = 31623; vector<int> primes; bool isComp[LIM + 1]; void linearSieve() { for (int i = 2; i <= LIM; i++) { if (!isComp[i]) { primes.push_back(i); } for (int p : primes) { if (1LL * i * p > LIM) break; isComp[i * p] = true; if (i % p == 0) break; } } }

外层循环的i从2走到LIM，遇到没被标记的就加入primes表。内层循环遍历当前已有的质数表，把i*p标记为合数。两个break缺一不可。

第一个break很好理解：ip超过LIM就没必要标记了，而且因为p是从小到大枚举的，后面更大的p只会让ip更大，直接终止循环。

第二个break才是线性筛的灵魂：当i % p == 0时，立即停止。为什么？

假设p能整除i，那么p就是i的最小质因子。此时设i = p * k，我们来考虑i的下一个质数q（q > p）。iq = p * k * q，这个数的最小质因子是p，不是q。按照“每个合数只被最小质因子筛掉”的原则，iq应该由外层走到kq时，内层枚举到p来筛掉，而不是现在由i和q来筛。所以现在必须break，把筛掉iq的机会留给未来。

所以“每个合数只被最小质因子筛一次”是怎么保证的？对任意合数x，设m是x的最小质因子，x = m * t。当外层循环i走到t时，内层枚举p从小到大，p=m时一定满足i%p==0（因为m|t），于是标记i*p=x后break，x被m筛掉。而x不会再被其他质因子筛掉，因为其他质因子对应的情况都被break拦截了。这个保证是严谨的，不是玄学。

如果你把if (i % p == 0) break;写成continue，结果依然正确，因为continue会让循环继续枚举更大的p，重复标记某些合数，复杂度退化。如果你干脆不写这个break，那所有质数都会一直乘到上界，重复标记的合数数量会回到接近埃氏筛甚至更多，线性性质就丢了。

4. 两种方案落地这道题

4.1 完整解题流程：筛表+试除判定

回到P5736。既然ai最大10^9，我们的策略就是：先筛出31623以内的质数表，然后对每个输入的数x，用质数表从小到大试除，只要p*p > x就停止。

判断函数的写法：

bool isPrime(int x) { if (x < 2) return false; for (int p : primes) { if (1LL * p * p > x) break; if (x % p == 0) return false; } return true; }

这里有一个微妙的逻辑：如果x本身就是质数，比如x=999999937（10^9以内最大的质数之一），试除过程中p*p始终小于x，一直到p超过√x才break，最后返回true。如果x是合数，它必然有一个不超过√x的质因子，这个质因子一定在primes表里（因为我们筛到了31623≥√x），试除到它时就会返回false。

还有一种边界情况：x本身就在质数表里，比如x=31623？31623不是质数（31623=3×10541），但x=31607这样接近31623的质数是存在的。这时p枚举到最接近√x的质数后，p*p>x触发了break，返回true，不需要真的把x本身筛进表里来判断。

这种“筛根号范围+试除判定”的组合，比我之前说的纯暴力快一个数量级，又比直接筛到1e9节省了海量内存，本质上是在时间、空间、代码复杂度三者之间找到了平衡点。

4.2 完整参考代码（C++）

把上面几段拼起来，就是一份可以直接提交的完整代码：

#include <bits/stdc++.h> using namespace std; const int LIM = 31623; vector<int> primes; bool isComp[LIM + 1]; void eratosthenesSieve() { for (int i = 2; i <= LIM; i++) { if (!isComp[i]) { primes.push_back(i); for (long long j = 1LL * i * i; j <= LIM; j += i) { isComp[j] = true; } } } } bool isPrime(int x) { if (x < 2) return false; for (int p : primes) { if (1LL * p * p > x) break; if (x % p == 0) return false; } return true; } int main() { eratosthenesSieve(); int n; cin >> n; vector<int> ans; for (int i = 0; i < n; i++) { int x; cin >> x; if (isPrime(x)) ans.push_back(x); } sort(ans.begin(), ans.end()); for (size_t i = 0; i < ans.size(); i++) { if (i) cout << ' '; cout << ans[i]; } cout << '\n'; return 0; }

如果你想用欧拉筛，只需要把eratosthenesSieve替换成前面的linearSieve即可，判断函数和主函数完全不用动。这两种筛法在LIM=31623时性能差距可以忽略，但代码逻辑都要能写对。

4.3 输出排序与重复数值的坑

这道题有个隐藏考点：题目要求“从小到大输出所有质数”，不是按输入顺序。我第一次做的时候，直接在读入循环里判断完就输出，完全没排序，结果WA。后来仔细读题才发现要sort一下。如果你的答案数组用的是vector，一句sort(ans.begin(), ans.end())就搞定了，但别忘了。

还有一个值得讨论的点：如果输入里有两个相同的质数，比如5出现了两次，输出时要输出两个5还是一个5？原题面说的是“从小到大输出所有质数”，并没有提“去重”，所以按竞赛惯例，每个数都要输出，也就是重复的质数要输两次。除非题面明确写了“不重复输出”或“输出不同的质数”，否则不要去重。很多新手在这里凭感觉自作主张去重，反而做错了。

5. 常见错误与调试经验

5.1 数组上限到底开多大

最典型的错误是LIM设得太小，比如随手写个10000或者sqrt(1000000000)时向下取整成31622。如果LIM=31622，万一输入的数是31622的平方附近的合数，它的质因子在质数表里没有完整覆盖，就可能误判。所以稳妥做法是：

注意：LIM取sqrt(所有输入数的上限)+1，确保向上取整。本题直接写成31623即可，写40000甚至100000也完全没问题，筛表越大，试除次数越多，但依然不会超时。

我见过有人写1000000，筛了一百万的质数表用来判断10^9以内的数，答案正确但预处理时间明显变长。筛表不是越大越好，够用就行，这也是刷题时需要注意的平衡感。

5.2 欧拉筛break条件写错的表现

如果你在欧拉筛里漏掉了if (i % p == 0) break;，程序不会WA，因为合数依然都被标记了。但它会导致大量重复标记，复杂度从O(n)退化为接近O(n log n)。你在LIM=31623时根本感觉不到差异，一旦拿到LIM=1e7的题，运行时间可能从0.1秒变成1秒多，直接TLE。

调试这类问题有个笨办法：小范围对比。把LIM改成50，分别跑埃氏筛和欧拉筛，打印每个合数被标记的次数。如果欧拉筛标记次数不是1，说明break位置写错了。我最初学线性筛时，就是靠这个办法一步步看懂“最小质因子”机制的。

5.3 边界值1和0的处理

1既不是质数也不是合数，0和负数更不用谈。判断函数开头那句if (x < 2) return false;就是专门挡这些边界的。虽然题面保证输入是正整数，但自测时我习惯把0和1都测一遍，防止自己写的判断逻辑在边界上出问题。

另外，质数表生成是从2开始的，数组isComp[0]和isComp[1]虽然默认false，但这两个位置永远不会被访问，也不会影响逻辑。如果某个版本的筛法代码从1开始循环，就可能出现把0和1当成质数的bug，看到这类代码要警惕。

我顺手整理了一张常见错误速查表，做题时对着排查效率很高：

6. 从P5736延伸出去：筛法的真正用武之地

6.1 最小质因子预处理与质因数分解

埃氏筛和欧拉筛标记合数的时候，可以顺手记录每个数的最小质因子。比如在标记isComp[ip]=true的同时，记录spf[ip]=p。在线性筛里，由于每个合数只被筛一次，记录的p一定是最小质因子。

有了spf数组，任意数x的质因数分解就变成O(log x)的机械操作：反复取spf[x]，然后x/=spf[x]，一边除一边统计。这对做约数个数、约数和、欧拉函数一类数论题帮助极大。P5736只让你判断质数，但“筛表时多记一个数组”的习惯，值得从这道题开始养成。

6.2 线性筛还能顺便求积性函数

线性筛的价值不止是筛质数。欧拉函数φ、莫比乌斯函数μ、约数个数d(n)这类积性函数，都能在线性筛的过程中同步算出来。以欧拉函数为例：

• 如果i与p互质，即i%p!=0，则φ(ip)=φ(i)(p-1)
• 如果i%p==0，则φ(i*p)=φ(i)*p

这两个递推式刚好和线性筛的循环结构完美匹配。所以你筛完质数表的同时，也把1到LIM所有数的欧拉函数算完了。这也是为什么说线性筛是一条“积性函数生产线”，而不只是一个质数筛选器。初学时不用急着掌握全部，但心里要清楚：今天学的if(i%p==0)break，后面会在无数个写法里再次出现。

6.3 什么时候该升级到Miller-Rabin

如果有一天你遇到ai上限是10^18的题，√上限就是10^9，筛表方案直接失效，因为内存和时间都不现实。这时候需要换工具：Miller-Rabin素性测试。它基于费马小定理和二次探测，在选定合适底数的情况下，可以在O(k log n)时间内高概率判断一个数是否为质数，k一般取3到7个底数就足够。

我不建议新手一上来就学Miller-Rabin，容易消化不良。更合理的路线是：先把P5736这类筛法题吃透，理解筛表的边界和复杂度，等到真正碰到大素数判定题时，再去补数学基础。知道“筛法失效时还有一条路”，就已经比很多只背模板的人强了。

最后分享一个我个人的小习惯：每次写完筛法代码，都会拿几个特殊值自测——0、1、2、4、9、一个较大的质数如999999937。这几组数据能一次性暴露数组越界、break条件错误和边界值遗漏三类问题。P5736本身不难，但它是一把很好的尺子，能把埃氏筛、欧拉筛、筛表上限、边界处理这几个点量得明明白白。把这题彻底吃透，后面再遇到区间质数、质因数分解甚至积性函数线性筛，你会觉得顺理成章。