哥德巴赫猜想的内容如下：
任意一个大于 44 的偶数都可以拆成两个奇素数之和。
例如：
8=3 58=3 5 20=3 17=7 1320=3 17=7 13 42=5 37=11 31=13 29=19 2342=5 37=11 31=13 29=19 23
现在，你的任务是验证所有小于一百万的偶数能否满足哥德巴赫猜想。
输入格式
输入包含多组数据。
每组数据占一行，包含一个偶数 nn。
读入以 00 结束。
输出格式
对于每组数据，输出形如 n = a b，其中 a,ba,b 是奇素数。
若有多组满足条件的 a,ba,b，输出 b−ab−a 最大的一组。
若无解，输出 Goldbach's conjecture is wrong.。
数据范围
6≤n<1066≤n<106
输入样例：
代码语言：javascript复制8
20
42
0输出样例：
代码语言：javascript复制8 = 3 5
20 = 3 17
42 = 5 37思路：直接平方枚举肯定超时，我们可以先线性预处理出1e6以内的质数，然后单个枚举，相当于打表map去看另外一个是不是也是奇素数~
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
const int N=1e6 10;
int n,pr[N],cnt;
bool st[N];
void init(int n){
for(int i=2;i<=n;i ){
if(!st[i])pr[cnt ]=i;
for(int j=0;pr[j]*i<=n;j ){
st[i*pr[j]]=1;
if(i%pr[j]==0)break;
}
}
}
int main(){
init(N);
while(cin>>n,n){
for(int i=0;pr[i]<n;i ){
int a=pr[i];
if(!st[n-a]){
printf("%d = %d %dn",n,a,n-a);
break;
}
}
}
}
