哥德巴赫猜想的内容如下：

任意一个大于 4 的偶数都可以拆成两个奇素数之和。

例如：

8=3+5
20=3+17=7+13
42=5+37=11+31=13+29=19+23

现在，你的任务是验证所有小于一百万的偶数能否满足哥德巴赫猜想。

输入格式

输入包含多组数据。

每组数据占一行，包含一个偶数 n。

读入以 0 结束。

输出格式

对于每组数据，输出形如 n = a + b，其中 a,b 是奇素数。

若有多组满足条件的 a,b，输出 b−a 最大的一组。

若无解，输出 Goldbach’s conjecture is wrong.。

数据范围

6≤n<106

输入样例：

8
20
42
0

输出样例：

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

线性筛

#include<cstdio>

const int N = 1000010;
bool st[N];
int prime[N / 10], cnt, n;

//线性筛100万内的所有素数
void get_prime(){
    for(int i = 2; i < N; i++){
        if(!st[i]) prime[cnt++] = i;
        for(int j = 0; prime[j] <= N / i; j++){
            st[prime[j] * i] = true;
            if(i % prime[j] == 0) break;
        }
    }
}

int main(){
    get_prime();
    while(scanf("%d", &n), n){

        bool flag = false;

        for(int i = 0; i < cnt; i++){

            if(!st[n - prime[i]]){
                printf("%d = %d + %d\n", n, prime[i], n - prime[i]);
                flag = true;
                break;
            }
        }

        if(!flag) puts("Goldbach's conjecture is wrong.");
    }
    return 0;
}