一天蒜头君猜想,是不是所有的偶数(除了 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 %dn",temp[i],n-temp[i]); break; } } } return 0; }
c/c++开发分享程序设计:找质数地址:https://blog.csdn.net/xlrll/article/details/110203724
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/596680.html