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; }
エラトステネスの篩を使って数えるだけ。