[C++知识库]C/C++语言100题练习计划 97——素数对

名人说：博学之，审问之，慎思之，明辨之，笃行之。——《中庸》
进度：C/C++语言100题练习计划专栏，目前97/100

一、问题呈现

1.问题描述

Problem Description

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

2.输入输出

Input

一个正整数 $n$。$1\le n\le 10000$。

Output

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

3.测试样例

样例1??
Sample Input

10

Sample Output

3 5
5 7

样例2??
Sample Input

100

Sample Output

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

样例3??
Sample Input

3

Sample Output

empty

二、源码实现

#include<iostream>
using namespace std;

bool isPrime(int x)//判断是否是素数的函数，返回0代表不是素数，返回1代表是素数
{
	//特断
    if(x<=1)
		return 0;
    if(x==2)
		return 1;
		
    //枚举可能的因数
    for(int i=2;i*i<=x;i++)
    {
    	//能被整除，存在除了1与自身以外的因数，不是素数
		if(x%i==0)
		{
			return 0;//返回0作为标记
		}
	}
	
    //否则就一定是素数，返回1作为标记
    return 1;
}

int main()
{
    int n;
    cin>>n;
    bool flag=0;//flag代表是否有素数对
    
    //i循环到n-2是为了防止另一个数超(i+2)过n的范围
    for(int i=1;i<=n-2;i++)
	{
		if(isPrime(i)&&isPrime(i+2))//如果找到素数对
		{
		    cout<<i<<" "<<i+2<<endl;//输出素数对
		    flag=1;//标记为素数对
		}
	}
        
        
    if(!flag)cout<<"empty"<<endl;//没有找到素数对，输出empty
    return 0;
}

★关于本题思路：

①首先，这道题由于 N 的范围不大，可以使用最简单的方法判断素数。

素数 指除了 1 和它本身以外不再有其他因数的自然数。
那我们可以直接枚举这个数所输入数字的可能的因数，如果除了 1 和它本身以外还有其他因数，那么它就不是素数了。

②其次，由于因数总是成对出现的，所以只需要枚举到这个数的算术平方根向下取整就可以了。

对于每一个在 1 到 n?2 之间的整数，如果它自身与它加 2 都是素数，那么它们就是一对素数对，将其输出即可。

③对了，不要忘了 1 不是素数， 2 是素数，需要特别判断一下。

明白了这些之后，应该就没啥大问题了，可以尝试编写程序了。

三、测试结果

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

--------------------------------
Process exited after 1.355 seconds with return value 0
请按任意键继续. . .

Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder）
如果对大家有帮助的话，希望大家能多多点赞+关注！这样我动力会更足哦！ ?( ′･?･` )比心