AOJ - Problem 1200 : Goldbach's Conjecture

AOJ 数論

4以上の偶数nについて、n=a+bとなる素数の組(a,b)がいくつあるか数える問題です。(2,3)と(3,2)のように順序が逆の組は区別されないので重複して数えないようにしましょう。この問題もエラトステネスの篩で素数表をあらかじめつくっておきましょう。

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 10000001;
char p[MAX];
vector<char> P;

void f(){
	for(int i=2 ; i < MAX ; i++ ) p[i] = 1;
	for(int i=2 ; i+i < MAX ; i++ ){
		if( p[i] ){
			for(int j=i+i ; j < MAX ; j += i ){
				p[j] = 0;
			}
		}
	}
	for(int i=2 ; i < MAX ; i++ ){
		if( p[i] ) P.push_back( i );
	}
}

int main(){
	int n;
	f();
	while( cin >> n , n ){
		int ans=0;
		for(int a=2 ; a < n ; a++ ){
			if( p[a] ){
				int b = n - a;
				if( a > b ) break;
				if( p[b] ) ans++;
			}
		}
		cout << ans << endl;
	}
}