sdnu1500.Problem_I (偶数写成两个质数的差 素数打表)

Description

Spring is coming, T_T.

       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 n identified the count of test cases(n<10^4). There is a even number x at the next n lines. The absolute value of x is not greater than 10^6.

Output

For each number x tested, outputs two primes a and b at one line separated with one space where a-b=x. If more than one group can meet it, output the minimum group（of course refers b）. If no primes can satisfy it, output 'FAIL'.

Sample Input

3
6
10
20

Sample Output

11 5
13 3
23 3

 把一个偶数写成两个质数的差   表打到1e7即可

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+7;
int prime[N/10];
bool vis[N];
int tot=0;
void Er()
{
    memset(vis,0,sizeof(vis));
    vis[1]=vis[0]=1;
    for(int i=2;i<N;i++)
    {
        if(!vis[i])
        {
            prime[tot++]=i;
            for(int j=i+i;j<N;j+=i)
                vis[j]=1;
        }
    }
}
int main()
{
    Er();
//    for(int i=0;i<10;i++)
//        cout<<prime[i]<<'\n';
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int it=lower_bound(prime,prime+tot,n)-prime;
        bool f=0;
        for(int i=it;i<tot;i++)
        {
            if(!vis[prime[i]-n])
            {
                f=1;
                cout<<prime[i]<<' '<<prime[i]-n<<'\n';
                break;
            }
        }
        if(!f)
            cout<<"FAIL"<<'\n';
    }
    return 0;
}