どん底から這い上がるまでの記録

どん底から這い上がりたいけど這い上がれない人がいろいろ書くブログ(主にプログラミング)

1200: Goldbach's Conjecture

Problem A:Goldbach's Conjecture

問題ページ

解き方

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

pytry3g.hatenablog.com

 

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