PIPIOJ 1053: 哥德巴赫猜想Ⅲ

素数筛，记住！
素数筛时间复杂度为nlogn

include <bits/stdc++.h>

using namespace std;
const int N=1e6+10;
bool P[N]; //判断从1-N的数哪些为素数，True代表不是素数
int idx[N]; //存储素数
int id;
void init(){
P[1]=1;
for(int i=2;i<=N;i++){
if(!P[i]){
idx[id++]=i;
for(int j=2i ; j<=N ;j+=i){
P[j]=1;
}
}
}
}
int main(){
init();
int n;
while(scanf("%d",&n)!=EOF){
for(int i=0 ;i<id&&idx[i]2<=n;i++){
if(!P[n-idx[i]]){
printf("%d %d\n",idx[i],n-idx[i]);
}
}
printf("\n");
}
}