hdu4715之素数筛选

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 673    Accepted Submission(s): 216

 

 

Problem Description

All you know Goldbach conjecture.That is to say, Every even integer greater than 2 can be expressed as the sum of two primes. Today, skywind present a new conjecture: every even integer can be expressed as the difference of two primes. To validate this conjecture, you are asked to write a program.

 

 

Input

The first line of input is a number nidentified the count of test cases(n<10^5). There is a even number xat the next nlines. The absolute value of xis not greater than 10^6.

 

 

Output

For each number xtested, outputstwo primes aand bat one line separatedwith one space where a-b=x. If more than one group can meet it, output the minimum group. If no primes can satisfy it, output 'FAIL'.

 

 

Sample Input

3

6

10

20

 

 

Sample Output

11 5

13 3

23 3

 

 

Source

2013 ACM/ICPC Asia Regional Online —— Warmup

#include<iostream>  
#include<cstdio>  
#include<cstdlib>  
#include<cstring>  
#include<string>  
#include<queue>  
#include<algorithm>  
#include<map>  
#include<iomanip>  
#define INF 99999999  
using namespace std;  
  
const int MAX=1000000+10;  
bool prime[MAX];  
int s[200]={2},size;  
  
void Prime(){//素数筛选   
    for(int i=2;2*i<MAX;++i)prime[2*i]=true;  
    for(int i=3;i*i<MAX;i+=2){  
        if(!prime[i]){  
            s[++size]=i;  
            for(int j=i*i;j<MAX;j+=i)prime[j]=true;  
        }  
    }  
}  
  
int main(){  
    Prime();  
    int t,n,m,i;  
    scanf("%d",&t);  
    while(t--){  
        scanf("%d",&n);  
        m=n>0?n:-n;  
        for(i=0;i<=size;++i){  
            if(!prime[s[i]+m])break;  
        }  
        if(n>0)printf("%d %d\n",s[i]+m,s[i]);  
        else printf("%d %d\n",s[i],s[i]+m);  
    }  
    return 0;  
}  

 

补充：软件开发 , C++ ,