输入数组，分解质数和

Question

Problem Description

给一个偶数n（6≤n≤100000）。问n能否分解为两个质数a、b的和。
如不能，输出”Impossible”（输出不要加双引号）。
若能，则输出a、b。若有多组解，则输出a最小的解。

Input

第一行有一个正整数T（T≤50），代表数据组数。
接下来T组数据，每组数组一行，为一个偶数n（6≤n≤100000）。

Output

对于每一组数据，在一行里输出两个整数a、b，中间用空格隔开。

Sample Input

5
6
10
16
20
100000

Sample Output

3 3
3 7
3 13
3 17
11 99989
Author

 Oyk 

#include<stdio.h>
int number(int x)
{int h;
    for(h=6;h<x;h++)
    {
    if(x%h==0)
    break;
    }
    if(h==x)
    return x;
    else 
    return 0;
}
void check(int k)
{int x;     
for(x=6;x<k;x++)
   { 
     if(number(x)!=0&&number(k-x)!=0)
     printf("%d %d",x,k-x);
     else
     printf("Impossible");
    }

} 
void main()
{int i,j,z,a[100];
scanf("%d",&i);
for(j=0;j<i;j++)
{
scanf("%d",&a[j]);
printf("\n");
}
for(z=0;j<i;j++)
{
check(a[z]);
}

}

Answer 1

#include <iostream>

using namespace std;


const int N = 50000;
const int MAXN = 100000;
int prime[N], flag[MAXN];

int getPrime() {
    int t = 0;
    for (int i = 0; i < MAXN; i++) {
        flag[i] = 1;
    }
    flag[0] = flag[1] = 0;
    for (int i = 2; i < MAXN; i++) {
        if (!flag[i]) {
            continue;
        }
        prime[t++] = i;
        for (int j = i * 2; j < MAXN; j += i) {
            flag[j] = 0;
        }
    }
    return t;
}

int main() {

int p = getPrime();

int tot;

cin >> tot;

while (tot--) {
    int n;

    cin >> n;
    bool flag = 0;

    for (int i = 0; i < p && prime[i] < n; i++) {
        int l = 0, r = p - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (prime[m] == n - prime[i]) {
                cout << prime[i] << " " << prime[m] << endl;
                flag = 1;
                break;
            }
            if (prime[m] < n - prime[i]) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        if (flag) {
            break;
        }
    }
    if (!flag) {
        cout << "impossible" << endl;
    }
}

}

Answer 2

打个表，列出50000以内的素数，然后随便搞

Answer 3

数据范围那么小 O(n) 线性筛一下素数， 然后不是随便搞了？

Answer 4

首先，“任一大于2的偶数都可写成两个素数之和”，这是强哥德巴赫猜想
至于怎么拆的话，这个很复杂啊。
http://baike.baidu.com/subview/1808/10645815.htm

Answer 5

这个列表啊。。有点《骗分导论》的感觉。