POJ - 2262 Goldbach’s Conjecture（埃氏筛）

POJ 2262 Goldbach’s Conjecture

先用埃氏筛法，筛出来100W之内的素数，然后直接就是哥德巴赫猜想，找到这个偶数的两个质数之和

#include<cstdio>
#include<cmath>
#include<cstring>const int N = 1000010;
bool isprime[N];
int prime[N];void get_primes()
{
    memset(isprime,1,sizeof isprime);int cnt=0;for(int i=2;i<=sqrt(N);i++){
    if(!isprime[i]) continue;prime[cnt++]=i;for(int j=i*2;j<=N;j+=i)isprime[j]=false;}
}int main()
{
    get_primes();int n;while(scanf("%d",&n)&&n){
    bool flag=false;for(int i=2;i<=n/2+1;i++){
    if(isprime[i]&&isprime[n-i]){
    flag=true;printf("%d = %d + %d\n",n,i,n-i);break;}}if(!flag) puts("Goldbach's conjecture is wrong.");}return 0;
}