信息学奥赛一本通：1403：素数对

【题目描述】

两个相差为2的素数称为素数对，如5和7，17和19等，本题目要求找出所有两个数均不大于n的素数对。

【输入】

一个正整数n(1≤n≤10000)。

【输出】

所有小于等于n的素数对。每对素数对输出一行，中间用单个空格隔开。若没有找到任何素数对，输出empty。

【输入样例】

100

【输出样例】

3 5
5 7
11 13
17 19
29 31
41 43
59 61
71 73

【参考程序一】

定义了一个函数 isShushu 用于判断一个整数 a 是否为素数。

以下是对代码的具体解释：

• bool flag = true;：初始化一个布尔类型的标志变量 flag，初始值为 true 。

• 接下来使用一个 for 循环，从 2 开始到 sqrt(a)（即 a 的平方根）。

• 在循环中，如果 a 能被当前的 i 整除，即 a % i == 0 ，则设置 flag 为 false ，并使用 break 终止循环。

• 最后，函数返回 flag 的值。如果 flag 为 true，表示 a 是素数；如果 flag 为 false，则表示 a 不是素数。

这段代码通过循环判断是否存在可以整除 a 的数，来确定 a 是否为素数。

经过两次素数的判断，若都满足素数的条件即为一组素数对

#include<bits/stdc++.h>
using namespace std;

bool isShushu(int a)
{
	bool flag=true;
	for(int i=2;i<=sqrt(a);i++)
	{
		if(a%i==0)
		{
			flag=false;
			break;
		}
	}
	
	return flag;
}

int main()
{
	int n,count=0;
	cin>>n;
	if(n>2)
	{
		for(int i=2;i<=n-2;i++)
		{
			if(isShushu(i)&&isShushu(i+2))
			{
				cout<<i<<" "<<i+2<<endl;
				count++;
			}
		}
		
		if(count==0)
		{
			cout<<"empty";
		}
	}
	else
	{
		cout<<"empty";
	}
	
	return 0;
 }

【参考程序二】

#include<bits/stdc++.h>
using namespace std;
int n,flag=1;
bool check(int n)//求素数
{
	for(int i=2;i<=sqrt(n);i++)
	{
		if(n%i==0)return false;
	}
	return true;
}
int main()
{
	cin>>n;
	for(int i=2;i<=n-2;i++)
	{
		if(check(i+2)&&check(i))//如果i和i+2都是素数就输出
		{
			cout<<i<<" "<<i+2<<"\n";
			flag=0;//flag归0
		}
	}
	if(flag)cout<<"empty";
	return 0;
}