0056 - Goldbach's Conjecture

#include <iostream>
using namespace std;

#define MAX 50000

bool is_prime[MAX+1];

void Sieve(void)	{
	for (int i=0; i<=MAX; ++i)
		is_prime[i]=true;
	is_prime[0]=is_prime[1]=false;
	for (int i=2; i<=MAX; ++i)
		if ( is_prime[i] )
			for (int j=i*2; j<=MAX; j+=i)
				is_prime[j]=false;
}

void Slove(int n)	{
	int count=0;

	for (int i=2; i<=n/2; ++i)
		if (is_prime[i] && is_prime[n-i] && i+(n-i)==n)	++count;
	cout << count << endl;
}

int main(void)	{
	int n;

	Sieve();
	while (cin >> n && n)
		Slove(n);
	return 0;
}

エラトステネスの篩を使って数えるだけ。