POJ 2909 Goldbach's Conjecture

Sample Output

1
2
1

CODE:

#include <iostream>
#include <cstdio>
#include <cstring>
#define REP(i, s, n) for(int i = s; i <= n; i ++)
#define REP_(i, s, n) for(int i = n; i >= s; i --)
#define MAX_N 50000 + 10

using namespace std;

int n, pri[MAX_N], ans = 0;
bool check[MAX_N];

void Prime(){
    memset(check, 0, sizeof(check));
    int tot = 0; check[1] = 1;
    REP(i, 2, 32770){
        if(!check[i]) pri[++ tot] = i;
        REP(j, 1, tot){
            if(i * pri[j] > 32770) break; check[i * pri[j]] = 1;
            if(i % pri[j] == 0) break;
        }
    }
}

int main(){
    Prime();
    while(scanf("%d", &n) != EOF){
        if(n == 0) break; 
        ans = 0;
        REP(i, 1, n / 2){
            if(!check[i] && !check[n - i]) ans ++;
        }
        printf("%d\n", ans);
    }
    return 0;
}            

POJ 2909 Goldbach's Conjecture

标签：