最近在帮学弟学妹备赛的时候洛谷 B2132 这道“素数对”被问到的频率特别高。它题目短、边界简单却把算法竞赛里最基础也最要命的几个点全串起来了素数判定怎么写才不出错、区间扫描的循环边界怎么收、输出格式在哪一步最容易翻车。很多新手一上来就想着上筛法、压常数结果反而在小坑里反复 WA。这篇文章我用 C 完整拆一遍 B2132 的三种做法从朴素判定到埃氏筛每段代码都告诉你“为什么要这样写”再附上我实际提交和帮别人改代码时踩过的坑。如果你正处于算法竞赛备考的入门冲刺阶段这道题值得你停下来认真啃透。1. 为什么备战算法竞赛要先啃下这道素数对1.1 题目到底在问什么先明确题面。B2132 说的是输入两个正整数 a 和 b输出区间 [a,b] 内所有的素数对。这里的“素数对”指的是两个素数相差正好为 2也就是数学里的孪生素数。比如 (3,5)、(5,7)、(11,13) 都是素数对而 (7,11) 虽然相邻且中间没有别的素数但差是 4不符合条件。如果整个区间内不存在这样的素数对就输出 -1。拿一组数据亲测一下输入3 10区间内的素数有 3、5、7能组成素数对的是3 5 5 7输入2 3区间内只有 2 和 3差的绝对值是 1不是素数对所以输出-1。这道题在洛谷里属于“数组、循环与判断”阶段的经典题表面上是数学题实际上考的是三个基本功判断单个素数、遍历区间、正确处理输出。这三个能力恰恰是后续刷动态规划、图论、数论题之前必须打牢的地基。很多同学觉得这题太简单直接跳过结果到了后面做“质因数分解”“哥德巴赫猜想相关题”时连最基础的素数判断都会写错这就很吃亏。1.2 适合谁刷、能练到什么如果你是以下三种情况B2132 值得专门刷一遍刚开始学 C、准备参加蓝桥杯或 CSP 入门组需要积累“必刷题”手感已经会一些语法但提交总是“答案错误”或“运行时错误”想找一个短小的题目集中排查边界问题想从“看得懂代码”过渡到“自己能把思路转成 C 提交”用这道题训练完整的解题流程。这道题有一个很友好的特性数据范围不算大朴素做法也能过。这意味着你能把注意力集中在“算法正确性”和“代码规范性”上不需要过早陷入“这题是不是要卡常”的焦虑。等把这道题彻底吃透再去看筛法、区间素数统计等进阶内容时你会觉得过渡非常自然。2. 核心思路拆解素数判定与区间扫描2.1 素数的判断边界必须刻进 DNA素数质数的定义是大于 1 的自然数中除了 1 和它本身以外不再有其他因数。注意这句话有三个关键词缺一不可大于 1所以 1 不是素数自然数负数、小数都不用考虑除了 1 和它本身如果存在第三个因数就不是素数。在 C 里写一个最基本的判断函数很多新手会写成这种bool isPrime(int x) { for (int i 2; i x; i) { if (x % i 0) return false; } return true; }这段代码对 2、3、5、7 这类数能正常工作但你一旦传入1循环一次都不执行直接返回true判断就错了。所以在循环之前必须加上if (x 2) return false;。这个边界是 B2132 最容易埋雷的地方因为当 a 从 1 开始i1和i23都需要判断如果判断函数漏掉x2就可能把 1 误判成素数导致输出一串错误结果。进一步优化判断循环的终止条件。如果 x 有一个大于 sqrt(x) 的因数 d那么 x/d 一定是小于 sqrt(x) 的因数也就是说因数总是成对出现。所以循环只要从 2 枚举到i * i x即可。这个结论一定要理解不只是背下来——它能把你判断单个素数的复杂度从 O(n) 降到 O(√n)是后面所有素数题的基础。2.2 直接扫描区间复杂度到底够不够B2132 最简单的思路是从 a 遍历到 b对每个 i 判断isPrime(i)和isPrime(i2)是否同时为真。这样做的复杂度是区间长度乘以单次判断复杂度即 O((b-a)·√b)。如果数据范围是1 ≤ a ≤ b ≤ 10^4这个复杂度大约是一万乘以一百也就是百万级别在 C 里跑起来轻松到可以忽略不计。如果数据范围放宽到1 ≤ a ≤ b ≤ 10^6最坏情况是一百万个数每个数要判断到 sqrt(10^6)1000那就是十亿次取模运算在 OJ 上很可能超时。所以如果题面没有明确给很小的范围更稳妥的做法是直接上筛法。下面表格可以帮你快速决策数据范围推荐方案理由a,b ≤ 10^4朴素 sqrt 判断代码短够快逻辑直观a,b ≤ 10^5朴素 sqrt 判断一般 1 秒内可过a,b ≤ 10^6埃氏筛/欧拉筛预处理后 O(1) 判断稳多次查询多组区间筛法 前缀和不只判断单点还能统计个数很多题目会在一开始给你一个较小的数据范围“劝你善良”但你不能保证换一道题还这么善良。所以 B2132 真正该练的是“先判断范围再选方案”的决策意识。2.3 筛法方案埃氏筛的适用边界埃氏筛的原理可以这样理解准备一个布尔数组初始认为所有数都是素数从 2 开始把每个素数的倍数全部标记为合数下一个未被标记的数必然是素数。vectorbool isPrime(maxN 1, true); isPrime[0] isPrime[1] false; for (int i 2; i * i maxN; i) { if (isPrime[i]) { for (int j i * i; j maxN; j i) { isPrime[j] false; } } }注意内层循环从i * i开始而不是从2 * i开始因为 i 的约数在小于 i 的素数筛选中已经被标记过了。这个小细节能省掉大量重复标记。埃氏筛的时间复杂度是 O(n log log n)在 n10^6 时表现非常稳定。用筛法做 B2132你需要先找到区间右端点 b然后筛到 b 为止。只要建好素数标记数组主循环里检查isPrime[i] isPrime[i2]就是 O(1) 的判断。这种方式还有个额外好处如果你在同一份代码里需要多次输出素数对筛一次可以反复用。3. 从读题到 AC三版代码逐行解析3.1 版本一最朴素的判断写法先给一份不含任何花哨操作、但完全正确的朴素版代码。这段代码适合刚学完函数和循环的同学目标是“先跑通再优化”。#include iostream using namespace std; 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 a, b; cin a b; bool found false; for (int i a; i 2 b; i) { if (isPrime(i) isPrime(i 2)) { cout i i 2 \n; found true; } } if (!found) { cout -1 \n; } return 0; }这里有几个细节要解释。主循环的结束条件是i 2 b因为如果 i2 已经超过 b就不可能构成区间内的素数对继续循环没有意义。这个写法比for (int i a; i b; i)然后在循环体里加if (i2 b) continue;更干净。另外一个容易忽略的点是判断isPrime(i)和isPrime(i2)的先后顺序。C 的运算符具有短路特性如果前面的isPrime(i)已经是 false后面的isPrime(i2)根本不会执行。这在单次判断里影响不大但如果你以后在判断条件里嵌入了耗时操作或数组越界风险的操作短路特性会帮你避免问题。3.2 版本二函数封装 循环边界优化朴素版已经能 AC但如果你想让代码更接近标准竞赛模板可以进一步优化把 Euler 循环边界提取成变量增加可读性对isPrime增加一个小的剪枝除 2 以外的偶数都不是素数。#include bits/stdc.h using namespace std; bool isPrime(int x) { if (x 2) return false; if (x 2) return true; if (x % 2 0) return false; for (int i 3; i * i x; i 2) { if (x % i 0) return false; } return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int a, b; cin a b; bool found false; int start max(a, 2); for (int i start; i 2 b; i) { if (isPrime(i) isPrime(i 2)) { cout i i 2 \n; found true; } } if (!found) cout -1 \n; return 0; }ios::sync_with_stdio(false)和cin.tie(nullptr)这两行是 C 竞赛输入输出的“提速组合拳”。很多新手不明白为什么写这两行简单说就是取消 cin 和 C 标准 IO 的同步让 cin/cout 的缓冲机制更快。在数据量几百上千时没差但到了几十万输入时就很有感。建议从现在开始形成肌肉记忆。start max(a, 2)是为了避免无意义的isPrime(1)调用。虽然朴素版也能处理 1但显式排除能让你在思考边界时更清晰。3.3 版本三埃氏筛预处理如果题目数据范围加大或者你希望练习筛法模板就用这一版。它的思路是先把[2, b]范围内的所有素数标记好然后在线性扫描中直接查表。#include iostream #include vector using namespace std; int main() { int a, b; cin a b; vectorbool isPrime(b 1, true); if (b 0) isPrime[0] false; if (b 1) isPrime[1] false; for (int i 2; i * i b; i) { if (isPrime[i]) { for (int j i * i; j b; j i) { isPrime[j] false; } } } bool found false; for (int i max(a, 2); i 2 b; i) { if (isPrime[i] isPrime[i 2]) { cout i i 2 \n; found true; } } if (!found) { cout -1 \n; } return 0; }注意vectorbool有一个著名的特殊性它不是普通的 bool 数组内部是压位存储的。使用时大部分场景没问题但如果你需要取地址或者把它当作标准容器操作会出现意想不到的问题。竞赛里为了省内存可以继续用vectorbool如果希望代码更通用可以换成vectorchar在判断时用isPrime[i] 1。我个人更推荐后者因为它的行为符合直觉也方便以后直接搬到更复杂的题目里。筛法版本的另一个细节如果输入是a1, b1isPrime数组长度为 2下标 0 和 1 都会被赋值为 false主循环因为i2b不成立直接跳过最后输出 -1。这个逻辑是安全的。如果输入是a10, b10同样不会误判。你可以在本地用这组数据测试确保不会出现数组越界。3.4 边界条件与输入输出细节B2132 的输入输出看似简单但有三处地方我见过太多次翻车。第一区间闭开性。题目说的是“a 到 b 之间”大多数版本是闭区间也就是包含 a 和 b。如果你的循环写的是for (int i a; i b; i)那么当 b 本身能和它前一个素数构成素数对时这一对会被错误地丢掉。比如输入3 5正确输出是3 5但开区间写法会什么都不输出直接打-1。第二空格和换行。每行输出两个数中间一个空格行末换行。有些同学图省事用cout i i 2 endl;endl虽然也能换行但它会强制刷新输出缓冲区在循环次数多的时候拖慢速度。竞赛里建议用\n。第三没有素数对时输出-1。这个条件一定要放在循环外面判断而不是每找到一个素数对就输出一次 -1。我见过有人把输出-1的语句写在if条件里面结果一次性输出好几个-1这属于逻辑结构没理清。用bool found标记是否找到最后统一判断是最稳妥的模式。4. 提交后的实战常见问题与排查技巧4.1 常见错误与排查速查表为了让你在 OJ 上看到报错时能第一时间定位我把 B2132 常见的错误整理成一张速查表错误表现可能原因排查方向输出结果中多了1 3素数判断函数没有处理x2检查 isPrime 开头是否有边界判断漏掉最后一组素数对循环用了开区间i b改成i 2 b结果全部正常但超时数据范围较大且用了 O(n·√n)改用筛法预处理输出-1-1或乱码多个-1被连续输出检查输出逻辑用 found 标记统一判断本地运行正确洛谷上 WA没有注意多组数据或输入格式确认题目是否只有一个测试点输入是否为一行两个整数数组越界 / RE筛法数组只开到 b 而不是 b1检查 vector 初始化长度和下标访问这张表不只是给 B2132 用的。很多区间类、判断类题目的 WA 原因翻来覆去就是这几类。建议你把它记下来刷别的题时也照着这个思路排查。4.2 为什么本地对了提交却 WA“我本地运行怎么测都对为什么一交就 WA”这是新手最常见的一句话。以 B2132 为例我帮人排查时发现过一个非常隐蔽的问题他把输入读取写成了cin a b;但题目给出的 a、b 顺序是反过来的或者是用空格和换行混合分隔的多个测试数据而他的代码只读了一行。还有一种情况是跨平台换行问题。洛谷评测环境基于 Linux标准输出以\n作为换行。如果你在本地用手动输入测试时敲了多余空格输出不会受影响但如果你的代码里写的是cout -1 endl endl;这种多余换行评测时可能会被判定为格式错误PE。所以提交前养成一个习惯不要加任何“为了美观”的多余空格或空行输出格式严格要求题目。另外int的范围是 2^31-1大约 21 亿。如果题目把 b 开到 10^9 甚至更大i * i在做循环判断时会溢出为负数导致死循环或错误判断。在 B2132 这种基础题里通常不会发生但一旦你跳到更难的素数题这个坑就会突然出现。解决办法是写成i x / i或者把变量类型换成long long。4.3 运行时间焦虑到底要不要用筛法很多同学刷 B2132 时明明朴素写法已经 AC 了看到题解区全在讲筛法又开始焦虑我是不是写得太弱了这里我想跟你聊点实在的。竞赛的最终目标是拿分不是炫技。如果你的数据范围支持朴素做法那就交朴素做法。把代码写清楚、把边界守好比硬套一个筛法却把数组开错导致 RE 强得多。我在备赛时会把“方案选择”的顺序定为先确认数据范围再选择复杂度最后才考虑常数优化和代码美观。但如果这道题你希望作为“素数筛”的练手题我不会拦你反而建议你多写一版筛法。因为筛法模板不练会生疏而后面很多题比如求区间内素数个数、求最小质因子都会用到。练 B2132 时写筛法成本低、反馈快性价比很高。换句话说用筛法不是因为它在这题里是必须的而是为了以后用得顺手。4.4 环境配置与本地调试建议在洛谷提交 C 代码时选对编译器版本也很重要。一般选 C17 或 C14 都行洛谷常见的编译器是 GNU G 系列。有些同学本地用的是 Dev-C一定要注意它的默认标准可能是 C98某些语法比如auto、vectorbool的列表初始化在老标准下会编译报错。建议在 Dev-C 的“工具 → 编译器选项”里把语言标准调成 C11 或更高。如果你用 VS Code 刷题我建议配置好 C/C 环境后再跑代码具体包括安装 C/C 扩展、配置 tasks.json 和 launch.json。第一次配置会花点时间但后面的调试体验非常好尤其是当你需要看 isPrime 函数里某个循环变量变化时断点调试能让你一眼看出逻辑错在哪。一个小技巧在本地调试 B2132 时先测小数据比如1 10、3 10、2 3再测一个无素数对的边界比如14 16。不要一上来就测1 10000因为那样只能看出“能不能出结果”看不出“边界逻辑是否正确”。把最小边界、最大边界、无解情况都测一遍比盲目随机数据可靠得多。5. 从一题到一类素数方向备考延伸5.1 变形题孪生素数、素数区间统计、哥德巴赫猜想B2132 刷完之后你可以顺着一根知识线继续往前延伸这样备考效率最高。第一个变形是“输出区间内所有相差为 d 的素数对”把固定差 2 改成变量 d。这个变形直接复用 B2132 的框架只需把i2改成id。第二个变形是“统计区间内素数对的总个数”不要求输出每一对只需输出数量。这时你可以把 for 循环里的cout改为cnt但要注意数对会重复吗不会因为每个起始位置只对应一个(i, i2)不存在重复计数问题。第三个变形是“验证哥德巴赫猜想把偶数拆成两个素数之和”。这题看似和素数对无关但核心还是素数判定遍历小于等于 n/2 的数 p判断isPrime(p) isPrime(n-p)是否成立。你会发现B2132 练出来的“双端点判断”模式换一层皮就能用过去这就是基础题的价值。另一个常见变形是“区间内素数个数”这会用到前缀和数组。先筛出素数再令pre[i] pre[i-1] (isPrime[i] ? 1 : 0)查询时输出pre[b] - pre[a-1]。如果你把 B2132 的筛法版稍加改动就能得到一个非常顺滑的前缀和模板。5.2 素数筛的常用模板沉淀备考到中后期你应该形成自己的“代码模板库”。对于素数这个方向至少要沉淀三样东西单个素数判断函数、埃氏筛、欧拉筛线性筛。前两个在 B2132 里已经练到欧拉筛建议你单独补一题练熟。欧拉筛和埃氏筛的区别在于埃氏筛会把同一个合数标记多次比如 12 会被 2 和 3 各标记一次而欧拉筛通过“每个合数只被它的最小质因子标记一次”来保证线性复杂度。模板大致长这样const int MAXN 1000000; vectorint primes; bool isComp[MAXN 1]; void eulerSieve(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; } } }关键在if (i % primes[j] 0) break;这行保证每个合数只被它的最小质因子筛掉。初次看可能觉得绕但结合“每个合数唯一被标记”这个目标去理解很快就能掌握。竞赛中很多数论题都会用到这个模板比如求 1 到 n 每个数的最小质因子、欧拉函数等提前沉淀好可以节省大量现场推导时间。5.3 刷题节奏建议基础题如何“榨干”价值最后聊聊备考节奏。我的建议是拿到一道基础题不要 AC 就立刻丢掉而是按三步走第一步写出朴素做法并 AC理解核心逻辑第二步尝试写出优化版本比如筛法对比两种方式的代码量和运行时间第三步改变题目条件改数据范围、改差值、改输出要求自己给自己出几道变形题。这样做一道题顶得上盲目刷五道同类题。因为你在刷题过程中被迫去理解“为什么”而不只是复制题解。B2132 特别适合用来练这个流程因为它足够短你可以轻松地在一次饭后时间里把三个版本都写完。我在实际帮别人改代码时发现很多人都卡在第三步。他们 AC 了基础版就急着做下一道结果遇到稍作变化的题还是不会。所以如果你现在正在备考真的建议把这道题当作“模板训练题”来对待哪怕多花半小时也要把筛法版写一遍、把边界测试补全。后续刷“素数个数”“孪生素数”“哥德巴赫猜想”时你会明显感觉到轻松很多。等你把单个素数判断、区间扫描、筛法预处理都内化成条件反射再回头看 B2132它就不再是一道“入门题”而是你整个数论刷题体系里最稳的一块基石。