hdu4715之素数筛选

Difference Between PrimesTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 673    Accepted Submission(s): 216


Problem DescriptionAll 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. 
InputThe 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.
 
OutputFor 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

361020

 
Sample Output

11 513 323 3

 
Source2013 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 99999999using 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;}