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

任意一个大于 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<10^6$
输入样例：

8
20
42
0

输出样例：

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

埃氏筛

#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <vector>
#include <set>
using namespace std;
const int maxn = 1e6+10;
typedef pair<int,int> pii;
typedef long long ll;

int N;
int P[maxn],tail;
bool vis[maxn];
void init(){
    for(ll i = 2;i<maxn;i++){
        if(!vis[i]){
            P[tail++] = i;
            for(ll j = i*i;j<maxn;j+=i){ //注意这里如果i是int，可能会爆
                vis[j] = true;
            }
        }
    }
}
int main(){
    init();
    while(scanf("%d",&N)){
        if(N == 0) break;
        int a = -1,b = -1;
        for(int i = 0;i<tail && P[i]+P[i]<=N;i++){
            if(!vis[N-P[i]]){
                a = P[i],b = N-P[i];
                break;
            }
        }
        printf("%d = %d + %d\n",N,a,b);
    }
    return 0;
}