程序设计：找质数

一天蒜头君猜想，是不是所有的偶数（除了 2），都可以用两个质数相加得到呢？于是聪明的蒜头君就找你来验证了。
输入格式
第一行输入一个整数 t 表示测试组数。
接下来 t 行，每行一个整数 n。
输出格式
输出两个整数，因为答案可能有多个，所有要求输出的这两个整数是所有答案中字典序最小的。
样例输入 复制
3
4
8
20
样例输出 复制
2 2
3 5
3 17
注意1不是质数
下面是代码里面有注释

#include<bits/stdc++.h>

using namespace std;
const int MAXN=1000010;
int sum=1,temp[MAXN];
bool f[MAXN],prime[MAXN];
bool check(int x){//判断素数 
	if(x==2||x==1) return false;
	for(int i=2;i<=sqrt(x);i++){
		if(x%i==0) return false;
	}
	return true;
}
void Get_prime(){//这里是先把素数打表 
	temp[0]=2;
    prime[2]=true;//标记 2是素数 
	for(int i=2;i<MAXN;i++){
		if(f[i]==false) { //如果i是false 说明i是素数 
			temp[sum++]=i;
			prime[i]=true;
			for(int j=i+i;j<MAXN;j=j+i){//那么i+k*i 就不是素数 
				f[j]=true;//标记i+k*i不是素数 
			}
			continue;
		}
		if(check(i)){ 
			prime[i]=true;
			temp[sum++]=i;
			for(int j=i+i;j<MAXN;j=j+i){
				f[j]=true;
			}
		}
	}	
}
int main(){
	fill(f,f+MAXN,false); 
	fill(prime,prime+MAXN,false);
	Get_prime();//素数打表 
	int t ;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		//从小到达找字典序最小的 
		for(int i=0;i<sum;i++){
			if(prime[n-temp[i]]==true){
				printf("%d %d\n",temp[i],n-temp[i]);
				break;
			}
		}
	}
	return 0;
}

本文地址：https://blog.csdn.net/xlrll/article/details/110203724