1200: Goldbach's Conjecture

Problem A:Goldbach's Conjecture

解き方

求めたい答えは与えられた４以上の偶数あるｎに対して、そのｎがある２つの素数の和と等しいような素数のペアの数を求めることである。まず素数を用意しなければいけないので、エラトステネスの篩を使って素数のリストを用意する。

pytry3g.hatenablog.com

さらに、その素数のリストから素数の値を取り出しておく。この問題では、(2, 3)、(3, 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]))