POJ 2262 Goldbach's Conjecture

Sample Output

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

线性筛素数
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 1000000 + 10
#define MAX_M 80000

using namespace std;

int n, pri[MAX_M];
bool check[MAX_N];

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

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

POJ 2262 Goldbach's Conjecture

标签：