先交代一下背景。洛谷 P5736 这道题标题全称是【深基7.例2】质数筛属于“深入浅出基础篇”题单里数学基础段的例题。很多第一次刷到它的朋友都会愣一下名字里明明写了“筛”可点进去一看输入的数最大能到 (10^9)这哪是让你直接开个布尔数组筛的样子说实话我第一次做这题也被迷惑过后来慢慢想明白这道题的真正考点不是“背一个筛法模板”而是“看清楚数据范围再从筛法里取一个合适的思想”。今天这篇东西就围绕这个题目把三种思路、两个大坑、以及一些提交时才会遇到的细节一次性聊透。这道题适合谁一类是刚学完埃氏筛、线性筛想找个题目练手的新手另一类是准备蓝桥杯、ACM 校赛想搞清楚“什么时候该用筛法什么时候别用筛法”的选手。甚至你只是单纯想复习一下质数判断的边界处理这篇也不会让你失望。我尽量用大白话把每一步为什么这么做讲清楚。1. 先别急着写代码把题目读透1.1 题面到底让你做什么题目本身很短输入一个整数 (n)然后给你 (n) 个不超过 (10^9) 的正整数要你按输入顺序输出其中所有的质数每个数之间用空格隔开。看起来简单就是一个判断质数的问题但“不超过 (10^9)”这六个字是整道题真正的分水岭。为什么这么说因为绝大多数教材在讲质数筛的时候都会选一个比较小的上限比如筛出 (10^6) 以内的所有质数。这时候开一个大小为 (10^61) 的布尔数组毫无压力。可这题的上限是 (10^9)如果你真按“筛法”的思路想要开一个长度 (10^9) 的数组先不谈洛谷的内存限制就算内存给够光是初始化这个数组的时间就足够让你超时。所以第一层理解应该是题目叫“质数筛”不代表你要写一个完整的筛子而是让你在判断质数这件事上用上“筛”的思想。另外还要注意输出格式。题目没说“行末空格怎么处理”一般洛谷对这种题是允许行末多余空格的但为了保险我也建议在输出的时候控制一下空格的位置后面会给出具体写法。1.2 “质数筛”这个名字的迷惑性“质数筛”这三个字很容易让人一上来就写埃氏筛或者欧拉筛。写完之后才发现怎么开数组开多大这个尴尬的处境我特别能理解因为我也犯过同样的错误。问题的根源在于传统筛法解决的是“求一个区间内有多少质数”的问题而这道题解决的是“判断若干个给定的数是不是质数”的问题。前者需要一次性把整个区间的合数标记出来后者只需要对每个数做快速判断。两者有交集但不等价。如果你把这两个问题混为一谈就会陷入“想要筛 (10^9)却开不了那么大数组”的死胡同。而正确的方向是把筛法的核心思想——用质数的倍数标记合数——从“筛满整个区间”降级成“筛出一个小素数表然后用小素数去试除那些大数”。也就是说这里真正被筛出来的不是所有输入数字而是一个足够小的质数集合。想通这一点整道题的思路就打开了。1.3 数据范围是唯一的指挥棒做题这些年我最大的一个体会是数据范围决定算法算法决定代码怎么写。P5736 的 (n \le 100)、数值 (\le 10^9)这两个条件放到一起就提示了你几条路单个数的试除复杂度是 (O(\sqrt{x}))(\sqrt{10^9} \approx 31623)乘上 (n100)总计算量在三百万级别。这个量级在任何评测机上都是一眨眼的事。如果先把 (\sqrt{10^9}) 以内所有质数筛出来用它们去试除这 100 个数那么单次判断最坏情况只需要遍历 (3401) 个质数这是 31623 以内实际质数的数量比从 2 试到 31623 快得多。如果你的目标是炫技写一个 Miller-Rabin 也没问题但对这道题来说属于大炮打蚊子。所以我的建议是先别急着选最复杂的做法先看数据范围。这也是洛谷题单里“数学基础”部分想培养的习惯——看到 (10^9) 就要条件反射地问自己数组能不能开循环能不能跑完要不要用 (O(\sqrt{n})) 级别的判断2. 解法一朴素试除法最不容易错的保底方案2.1 判断单个质数的写法假设你什么筛法都不会只懂得质数的定义大于 1 的自然数除了 1 和它本身以外不再有其他因数。那么判断一个数 (x) 是不是质数最直接的办法就是从 2 开始一直试到 (x-1)看有没有能整除的。稍微优化一点只需要试到 (\sqrt{x})因为如果 (x) 有一个因数 (a\sqrt{x})那必然存在另一个因数 (bx/a\sqrt{x})只要检查较小的那个就够了。这个优化是所有质数判断的基础。写成代码就是这个样子#include cstdio 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; } int main() { int n, x; scanf(%d, n); bool first true; while (n--) { scanf(%d, x); if (isPrime(x)) { if (!first) putchar( ); first false; printf(%d, x); } } putchar(\n); return 0; }这里我用了一个first变量来控制空格输出避免行末多余空格。洛谷虽然经常允许行末空格但万一哪天遇到严格判题的模式这种写法就不容易出问题。养成好习惯不亏。2.2 i*i 的溢出风险与写法改进上面的代码里有一个细节值得单独说一说i * i x这种写法在 (x10^9) 这个范围里不会出问题因为 (31623^2 \approx 10^9)距离 int 的上限 (2147483647) 还差得远。但是如果你的题目范围变成 (10^{18})或者你用了int而循环变量正好是inti * i就可能溢出成负数导致死循环。所以更稳妥的写法是改成i x / i。这个写法不会溢出每次判断只用一次整数除法性能也没有损失。或者把i声明成long long也能规避问题。我个人推荐的写法是for (int i 2; i x / i; i) { if (x % i 0) return false; }还有一种更微妙的优化对于偶数直接特判然后从 3 开始每次步长为 2。这样可以省掉一半的取模运算。对这道题来说三百万次取模其实无所谓但如果以后遇到 (T) 组数据每组都要判断大质数步长为 2 的写法就会显得更有价值bool isPrime(int x) { if (x 2) return false; if (x % 2 0) return x 2; for (int i 3; i x / i; i 2) { if (x % i 0) return false; } return true; }这个版本的逻辑是先排除所有偶数再从 3 开始逐个检查奇数因子。对于 (x2) 要单独返回true对于 (x4)、(x6) 这类偶数x % 2 0且x ! 2直接返回false。这个细节很容易漏写的时候要格外注意。2.3 朴素法在这个数据范围下的表现(n100)每个数最大 (10^9)用朴素试除法最坏情况下每个数要循环约 (31623) 次。总循环次数 (100 \times 31623 3162300)也就是三百多万次。现代 CPU 一秒钟可以执行几亿次简单运算所以这个量级跑起来飞快在洛谷上连 0.01 秒都用不到。这意味着什么意味着对这道题来说朴素试除法其实已经是完全够用的解法。你甚至不需要用什么筛法直接暴力判断就能过。很多新手总觉得自己必须写出“高级”的算法才安心但实际上竞赛里最忌讳的就是过度设计。算法够用就行关键是性能瓶颈要判断准确。我见过不少人在 P5736 里写 Miller-Rabin代码长达上百行最后也能过但完全没有必要。这道题的教学目标就是让你理解“筛”不只是一种固定的模板更是一种思想。能用简单的办法解决就别硬上复杂的模板。3. 解法二把筛法缩小到 sqrt(1e9)再用来除3.1 为什么只筛到 sqrt(最大值)现在来说说真正贴合“质数筛”这个名字的解法。既然不能开 (10^9) 的数组那就退一步如果一个合数 (x) 有一个质因数 (p)那么 (p) 一定不超过 (\sqrt{x})。也就是说所有能被 (x) 整除的质因数都在 ([2, \sqrt{x}]) 这个范围里。所以一个很自然的思路是先把 (\sqrt{10^9} \approx 31623) 以内的所有质数筛出来得到一张素数表。然后对于每个输入的数 (x)只用这张素数表里的质数去试除。一旦发现某个质数 (p) 满足 (p \times p x)就说明连这个质数都开始大于 (\sqrt{x}) 了后面更大的质数更不可能整除 (x)直接结束循环。这样做的好处是双重的第一筛法的部分只需要把 (31623) 以内的合数标记出来内存开销极小第二试除的时候不需要从 2 到 (\sqrt{x}) 每个数都去模只需要用大约 (3401) 个质数去试。如果把判断过程中的取模操作看作主要开销素数表方案比朴素试除快一个数量级。3.2 用素数表判断大数的过程整个流程可以拆成两个阶段。第一阶段筛出素数表。用经典的埃氏筛上限设为MAXP 31623也就是int(sqrt(1e9))左右。代码里我建议多开一点比如取int(sqrt(1e9)) 1防止误差。筛法本身很简单从 2 开始如果当前数没被标记为合数就把它加入素数表然后把它的平方、平方加上它本身、再加它本身……一直往后标记。这里从平方而不是从两倍开始标记是一个常规优化因为比较小的倍数已经在更小质数处理时被标记过了。第二阶段用素数表对每个输入数字做判断。核心循环长这样bool isPrimeByTable(int x) { if (x 2) return false; for (int p : primes) { if ((long long)p * p x) break; if (x % p 0) return false; } return true; }注意这行(long long)p * p。虽然 (p) 最大不过 (31623)乘积不会超过 (10^9)并不会溢出 int但写成long long是给以后的题目留后路。这种“顺手不溢出”的习惯在竞赛里能帮你省下很多排查时间。我实测过一次用这种素数表方案处理 100 个数耗时几乎是 0.000 秒级别肉眼根本感知不到。3.3 完整代码C 与 Java 两个版本C 完整代码#include cstdio #include vector using namespace std; const int MAXP 31623; vectorint primes; bool isComp[MAXP 1]; void sieve() { for (int i 2; i MAXP; i) { if (!isComp[i]) { primes.push_back(i); if ((long long)i * i MAXP) { for (int j i * i; j MAXP; j i) { isComp[j] true; } } } } } bool isPrime(int x) { if (x 2) return false; for (int p : primes) { if ((long long)p * p x) break; if (x % p 0) return false; } return true; } int main() { sieve(); int n, x; scanf(%d, n); bool first true; while (n--) { scanf(%d, x); if (isPrime(x)) { if (!first) putchar( ); first false; printf(%d, x); } } putchar(\n); return 0; }Java 版本也给出一个import java.util.*; public class Main { static final int MAXP 31623; static ListInteger primes new ArrayList(); static boolean[] isComp new boolean[MAXP 1]; static void sieve() { for (int i 2; i MAXP; i) { if (!isComp[i]) { primes.add(i); if ((long) i * i MAXP) { for (int j i * i; j MAXP; j i) { isComp[j] true; } } } } } static boolean isPrime(int x) { if (x 2) return false; for (int p : primes) { if ((long) p * p x) break; if (x % p 0) return false; } return true; } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); sieve(); StringBuilder sb new StringBuilder(); while (n-- 0) { int x sc.nextInt(); if (isPrime(x)) { sb.append(x).append( ); } } String res sb.toString().trim(); if (!res.isEmpty()) { System.out.println(res); } else { System.out.println(); } System.out.flush(); } }这里我遇到过一个小坑如果输入的 100 个数里一个质数都没有sb.toString().trim()会变成空字符串println()也能正常工作但如果你直接输出没有问题。不过一定要记得trim()不然最后会多出一个空格。这个细节虽然不影响 AC但看着输出结果心里总觉得别扭。3.4 复杂度对比快在哪朴素试除的最坏情况每个数循环到 (\sqrt{x})大约 31623 次。素数表方案每个数最多遍历 3401 个质数。看起来只快了不到 10 倍但在极限数据下差距会放大。如果题目变成 (n10^5)每个数还是 (10^9)朴素试除就是 (10^5 \times 31623 \approx 3.16 \times 10^9) 次循环大概率 TLE而素数表方案是 (10^5 \times 3401 \approx 3.4 \times 10^8) 次循环配合步长为 2 的小优化勉强能跑。当然这是后续扩展题的思路P5736 本身用不上这么大的 (n)但作为训练理解复杂度的这种差异还是很有价值的。4. 解法三线性筛到底什么时候用4.1 欧拉筛的原理一句话讲清既然题目名字里有“筛”那还是免不了要提一下线性筛欧拉筛。埃氏筛的问题是同一个合数可能被多个质数重复标记比如 12 既会被 2 标记又会被 3 标记这就带来了额外的开销。欧拉筛的改进在于每个合数只被它的最小质因数筛掉一次。怎么做到在遍历每个数 (i) 的时候让它去乘上已经筛出的质数得到合数 (i \times primes[j])然后标记。关键是在标记的过程中一旦发现 (primes[j]) 能整除 (i)就停下来。因为此时 (primes[j]) 已经是 (i) 的最小质因数如果继续用更大的质数去乘 (i)得到的合数的最小质因数就不是那个更大的质数而是 (primes[j])应该留到后面再筛。欧拉筛的代码相比埃氏筛更精简逻辑却更难理解vectorint primes; bool isComp[100000005]; void linearSieve(int n) { for (int i 2; i n; i) { if (!isComp[i]) primes.push_back(i); for (int j 0; j primes.size() i * primes[j] n; j) { isComp[i * primes[j]] true; if (i % primes[j] 0) break; } } }这段代码看起来很美但代价是内存占用和初始化时间。真要筛 (10^9)光布尔数组就要 1GB这还不算时间开销。4.2 这道题为什么不推荐线性筛原因很直接数据范围不合理。P5736 的输入上限是 (10^9)如果你要筛出 (10^9) 以内所有质数内存上就过不了关时间上更是不可接受。哪怕你用 bitset 压缩内存理论上能把布尔数组压到 125MB但初始化这么多状态位也需要时间对 100 个输入数字来说纯属浪费。所以这道题的正确姿势是用“素数表试除”而不是“筛满整个区间”。我理解很多教程会把“质数筛”和“线性筛”画等号但题目真正想让你学会的是筛到哪一步为止取决于你的判断目标。目标是一个小区间的所有质数那就筛小区间目标是判断几个大数那就筛出试除所需的小素数表就行。4.3 什么情况下才该用线性筛线性筛真正发光的场景是要求出 (10^7) 或 (10^8) 以内所有质数的个数、前缀和、最小质因数等并且题目允许你开相应大小的数组。比如你要求 (10^7) 内的欧拉函数和质数个数埃氏筛会慢一些欧拉筛就能做到 (O(n)) 的线性复杂度而且可以在筛的过程中顺便计算积性函数。我的建议是把欧拉筛作为基本功背熟但在写任何题目之前先问自己三个问题第一数据范围允许我开这么大的数组吗第二我是需要区间内所有质数还是只需要判断少量数字第三如果只需要判断少量数字用素数表试除是不是已经足够问完这三个问题选型就不会有太大偏差。5. 提交通关记录与踩坑复盘5.1 我第一次提交是怎么 WA 的说说我自己的黑历史。第一次做 P5736 的时候我还没看数据范围顺手写了一个埃氏筛到 (10^6) 的版本然后把每个输入的数和素数表比较发现大质数全都判断不出来WA 得非常彻底。后来冷静下来才意识到素数表只筛到 (10^6)但输入的质数可能大到接近 (10^9)我拿一张只有 (10^6) 以内素数的表去判断当然会出错。这个教训让我明白了一个道理当判断一个数 (x) 是否为质数时试除的边界是 (\sqrt{x})不是某个我拍脑袋定的上限。如果你筛到 (10^6)就只能正确判断所有 (x \le 10^{12}) 的数。这本质上是一个数学约束不是想当然就能绕过的。如果是在本地调试我建议你用一些已知的质数来检查边界比如 (999999937) 是一个接近 (10^9) 的质数(99999991) 也是。把这些数放进测试数据里能有效检查你的素数表是否够用。5.2 常见问题速查表问题原因解决方案1 被错误地输出为质数没处理x 2的边界判断函数开头加if (x 2) return false;输出末尾多一个空格每次判断成功都直接输出用first变量或先拼字符串再trim()大质数被判断成合数素数表上限不够没有覆盖到 (\sqrt{x})素数表至少筛到 (\sqrt{10^9})小偶数比如 2 被判错奇偶特判时漏了x 2特判if (x % 2 0) return x 2;想知道为什么数组开不了上限太大超出内存限制改用素数表试除或试除法用i * i x死循环潜在溢出风险改成i x / i5.3 输入输出上的小优化洛谷很多题都有输入规模不大但读入频繁的情况P5736 的 (n) 只有 100用cin和scanf差别不大。但如果你想养成好习惯可以记住几个原则C 里如果n很大优先用scanf/printf或者是关闭同步的cin/cout。ios::sync_with_stdio(false); cin.tie(nullptr);这两行可以显著提升 C 流式输入输出的效率。Java 里如果输入量大别用Scanner改用BufferedReader。Scanner虽然方便但性能只有BufferedReader的几分之一。(n100) 感觉不出来但 (n10^5) 就会明显卡顿。输出的时候能用StringBuilder拼接就不要一个接一个print频繁刷新缓冲区是性能杀手。这套输入输出优化的思路在刷完这道题之后还会反复用到所以我觉得有必要在这里写一嘴。6. 这道题还能带出哪些延伸知识6.1 从质数筛到区间筛P5736 只要求判断 100 个数但如果题目换成“请你输出区间 ([L, R]) 内的所有质数”其中 (R-L \le 10^6)但 (R) 本身可以达到 (10^{12})你想开一个从 (R) 开始的数组也开不了。这时候就要用区间筛先筛出 (\sqrt{R}) 以内的质数然后用这些质数去标记区间 ([L, R]) 内的合数最后剩下的就是区间质数。核心思想和今天这道题的素数表试除是一脉相承的大范围内开不了数组就把作用范围限制在 (\sqrt{}) 级别的小区间里。P5736 正是这条路的引子。建议大家做完这道题之后去找几道区间筛的题目练手比如 POJ 2689 的 Prime Distance或者洛谷上的区间质数统计题。你会很快发现今天学的这个素数表思路在那些题里几乎是标准解法。6.2 面试和竞赛里更常见的质数判断方式在面试场景里手写一个判断质数的函数是很常见的。面试官通常不会要求你写 Miller-Rabin但会关注几个点边界条件是否处理完整、循环边界是否写成i * i且有没有溢出隐患、有没有意识到偶数可以加速。这三个点在这道题里全都涉及了所以认真做过 P5736 的人应付这类手写题会很从容。如果题目进一步升级让你判断一个 (10^{18}) 级别的数是否为质数那就进入 Miller-Rabin 的领域了。这个算法基于费马小定理和二次探测定理原理不复杂但实现的时候需要处理好随机数和快速幂。我不建议初学者一上来就碰它先把今天这种基础判断练扎实后面自然会水到渠成。6.3 刷题建议什么时候背模板什么时候想原理最后这点是我的个人体会。很多新人喜欢把质数筛的模板背下来然后遇到质数题就往上套结果像 P5736 这样看似“叫筛法却不让筛”的题一出现就直接懵掉。其实模板背熟是必要的但更重要的是记住模板背后的适用边界。埃氏筛和线性筛解决的是“区间内找质数”试除法解决的是“单点判断”两者有自己的边界条件。往后再刷题看到题目里的数据范围先形成条件反射如果 (n \le 10^7) 且要统计区间质数考虑埃氏筛或线性筛如果数字本身很大但不是很多考虑素数表试除如果数字很大且很多考虑 Miller-Rabin 或区间筛。这套“看数据范围选算法”的肌肉记忆就是在这类基础题里慢慢练出来的。最后再分享一个小技巧。每次提交前我都会在本地自造几组边界数据全是 2 和 3 的小数据、包含 1 的数据、包接近 (10^9) 质数的数据、全是合数的数据。跑完这几组再提交基本不会出现第一次 WA 的尴尬。这道题里的坑我几乎全踩了一遍写出来就是希望你少走几步冤枉路。把基础打好后面的区间筛、线性筛扩展题你会学得更顺手。