Difference Between Primes（素数打表，素数表与数表通用）

喜欢ヅ旅行 2022-08-01 13:53 148阅读 0赞

# Difference Between Primes #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 2735    Accepted Submission(s): 768**

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][2013 ACM_ICPC Asia Regional Online _ Warmup]

**感觉这个题特别好！注意数据大！**

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<iostream>
    using namespace std;
    int prime[1000050],num[1000050];
    int main()
    {
        int t,n,len=0,k,l,f,f1,m;
        long long i,j;
        memset(num,0,sizeof(num));
        memset(prime,0,sizeof(prime));
        for(i=2;i<=sqrt(1000050);i++)
        {
            for(j=i*i;j<=1000050;j+=i)
            {
                num[j]=1;
            }
        }
        for(i=2;i<=1000050;i++)
        {
            if(!num[i])
            {
                prime[len++]=i;
            }
        }
       /* for(i=0;i<5;i++)
        {
            cout<<prime[i]<<" ";
        }*/
        cin>>t;
        while(t--)
        {
            f=f1=0;
            cin>>n;
            m=n;
            if(n<0)
            {
                n=-n;
            }//注意负数！
            if(n==0)
            {
                cout<<"2 2"<<endl;
                continue;
            }
            for(k=0;k<len;k++)
            {
               if(!num[prime[k]+n])//这样比较快哦！
               {
                   if(m<0)
                   {
                       cout<<prime[k]<<" "<<prime[k]+n<<endl;;
                   }
                   else
                   {
                       cout<<prime[k]+n<<" "<<prime[k]<<endl;
                   }
                   f=1;
                   break;
               }
            }
            if(!f)
            {
                cout<<"FAIL"<<endl;
            }
        }
    }

** **

[2013 ACM_ICPC Asia Regional Online _ Warmup]: http://acm.hdu.edu.cn/search.php?field=problem&key=2013+ACM%2FICPC+Asia+Regional+Online+%A1%AA%A1%AA+Warmup&source=1&searchmode=source