题目连接

http://acm.hdu.edu.cn/showproblem.php?pid=4715

Difference Between Primes

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

素数筛选+二分判断。。

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<vector>

#include<map>

using std::map;

using std::min;

using std::find;

using std::pair;

using std::vector;

using std::multimap;

using std::lower_bound;

#define pb(e) push_back(e)

#define sz(c) (int)(c).size()

#define mp(a, b) make_pair(a, b)

#define all(c) (c).begin(), (c).end()

#define iter(c) __typeof((c).begin())

#define cls(arr, val) memset(arr, val, sizeof(arr))

#define cpresent(c, e) (find(all(c), (e)) != (c).end())

#define rep(i, n) for(int i = 0; i < (int)n; i++)

#define tr(c, i) for(iter(c) i = (c).begin(); i != (c).end(); ++i)

const int N = 1000000;

const int INF = 0x3f3f3f3f;

int tot, prime[N + 10];

bool is_prime[N + 10];

inline void init() {

    tot = 0;

    rep(i, N) is_prime[i] = true;

    is_prime[0] = is_prime[1] = false;

    for(int i = 2; i <= N; i++) {

        if(is_prime[i]) {

            prime[tot++] = i;

            for(int j = 2 * i; j <= N; j += i) is_prime[j] = false;

        }

    }

}

void solve(int x) {

    rep(i, tot) {

        int p = lower_bound(prime, prime + tot, prime[i] + x) - prime;

        if(prime[i] + x == prime[p]) {

            printf("%d %d\n", prime[p], prime[i]);

            return;

        }

    }

    puts("FAIL");

}

int main() {

#ifdef LOCAL

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w+", stdout);

#endif

    init();

    int t, n;

    scanf("%d", &t);

    while(t--) {

        scanf("%d", &n);

        solve(n);

    }

    return 0;

}

秒客网

hdu 4715 Difference Between Primes