当前位置：首页 > news >正文

实用指南：老题新解|素数对

news 2026/3/26 18:31:47

《信息学奥赛一本通》第131题：素数对

题目描述
定义两个相差为 $2$ 的素数称为素数对，如 $5$ 和 $7, 17$ 和 $19$ 等，要求找出所有两个数均不大于 $n$ 的素数对。
输入格式
一个正整数 $n$ 。 $\le n \le 10000$ 。
输出格式
所有小于等于 $n$ 的素数对。每对素数对输出一行，中间用单个空格隔开。若没有找到任何素数对，输出 empty。
输入输出样例 #1
输入 #1
10
输出 #1
3 5
5 7
输入输出样例 #2
输入 #2
100
输出 #2
3 5
5 7
11 13
17 19
29 31
41 43
59 61
71 73
输入输出样例 #3
输入 #3
3
输出 #3
empty

大家好，我是莫小特。
这篇文章给大家带来《信息学奥赛一本通》中的第 131 题：素数对。

一、题目描述

洛谷的题号是：B2132 素数对

二、题意分析

这道题是信息学奥赛一本通练习题的第 131 题。

根据输入格式的描述，输入只有一个整数 n，数据范围： $\le n \le 10000$ ，使用 int 类型。

int n;
cin>>n;

输入完成后，我们来分析题意，根据题目描述，我们需要找到两个相差为 2 的素数对，并将所有不大于 n 的素数对输出。

所以我们需要使用 for 循环变量遍历，从 2 开始到 n。

for(int i=2;i<=n;i++)
{
}

中间加上判断素数的函数，只要符合就输出数据。

素数的函数写法如下，孰能生巧，直接写出，根据素数的特点写出函数：

bool pdss(int k)
{
if(k==1) return false;
else
{
//除1和本身的数以外能找到整除的数
for(int i=2;i<k;i++)
{
if(k%i==0) return false;
}
return true;
//返回真
}
}

将函数添加进主函数中。

for(int i=2;i<=n;i++)
{
//符合素数特点 输出i和i+2
if(pdss(i)==true&&
pdss(i+2)==true)
{
cout<<i<<
" "<<i+2<<endl;
}
}

如果不存在素数对，就输出 empty，可以加上一个标记，如果找到就标记为一个数，最后判断这个数据即可。

int flag=1;
for(int i=2;i<=n;i++)
{
//符合素数特点 输出i和i+2
if(pdss(i)==true&&
pdss(i+2)==true)
{
cout<<i<<
" "<<i+2<<endl;
//找到数据将数据置为其他数
flag=0;
}
}

判断 flag 是否为 1，如果为 1，则输出 empty。

if(flag==1)
{
cout<<
"empty";
//不存在就输出empty
}

按照样例输入对数据进行验证。

符合样例输出，到网站提交测评。

发现有两个错误点，检查代码，发现是主函数的循环出现了问题，因为要输出 i+2，而 i+2 要到 n 就停止，但循环中却写了 n，因此最终的 i 会到 n+2 ，所以在主函数中修改。

for(int i=2;i<=n-2;i++)

再次提交。

测试通过！

三、完整代码

该题的完整代码如下：

#include<iostream>#include<bits/stdc++.h>using namespace std;bool pdss(int k){if(k==1) return false;else{//除1和本身的数以外能找到整除的数for(int i=2;i<k;i++){if(k%i==0) return false;}return true;//返回真}}int main(){int n;cin>>n;int flag=1;for(int i=2;i<=n-2;i++){//符合素数特点 输出i和i+2if(pdss(i)==true&&pdss(i+2)==true){cout<<i<<" "<<i+2<<endl;//找到数据将数据置为其他数flag=0;}}if(flag==1){cout<<"empty";//不存在就输出empty}return 0;}