読者です 読者をやめる 読者になる 読者になる

AOJ 0056 Goldbach's Conjecture

ゴールドバッハ予想 | Aizu Online Judge


i番目とn-i番目の数が素数なら二つの和がnになるのでカウント

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

#define SIZE 50001

int main() {
	bool prime[SIZE];
	fill(prime, prime + SIZE, true);
	prime[0] = prime[1] = false;
	for (int i = 2; i * i < SIZE; i++) {
		for (int j = 2; j * i < SIZE; j++) {
			if (!prime[i * j]) continue;
			prime[i * j] = false;
		}
	}

	int n, count;
	while (cin >> n) {
		if (n == 0) break;

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