1053: 哥德巴赫猜想Ⅲ

两种筛法

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
bool vis[N];
int prime[N];
int n;
int k=0;
//void sieve(){
//	vis[1]=1;
//	for(int i=2;i<=N;i++){
//		if(!vis[i]){
//			prime[k++]=i;
//			for(int j=i+i;j<=N;j+=i){
//				vis[j]=1;
//			}
//		}
//	}
//}
void sieve(){vis[1]=1;for(int i=2;i<=N;i++){if(!vis[i])prime[k++]=i;for(int j=0;j<k;j++){if(prime[j]*i>N)break;else {vis[prime[j]*i]=1;}if(i%prime[j]==0)break;}}
}
int main(){sieve();while(scanf("%d",&n)!=EOF){for(int i=0;i<k;i++){if(prime[i]>n/2)break;if(vis[n-prime[i]]==0){printf("%d %d\n",prime[i],n-prime[i]);}}printf("\n");}return 0;
}