Problem A:Goldbach's Conjecture
解き方
求めたい答えは与えられた4以上の偶数あるnに対して、そのnがある2つの素数の和と等しいような素数のペアの数を求めることである。 まず素数を用意しなければいけないので、エラトステネスの篩を使って素数のリストを用意する。
さらに、その素数のリストから素数の値を取り出しておく。 この問題では、(2, 3)、(3, 2)といった素数のペアは重複になっておりカウントしないので、 素数のペアの数を求める際は、2からn/2までを探索する。
コード(python)
import bisect primes = [0, 0] + [1] * 32767 for i in range(2, 182): if primes[i]: for j in range(i*i, 32769, i): primes[j] = 0 prime_values = [i for i, v in enumerate(primes) if v] while True: n = int(input()) if n == 0: break eov = bisect.bisect(prime_values, n//2) print(sum(primes[n-p] for p in prime_values[:eov]))