Problem:


 ゴールドバッハ予想

 ゴールドバッハ予想とは「6 以上のどんな偶数も、2 つの素数 (*1) の和として表わすことができる」というものです。

たとえば、偶数の 12 は 12 = 5 + 7 、18 は 18 = 5 + 13 = 7 + 11 などと表すことができます。

 和が 134 となる 2 つの素数の組み合せをすべて書き出すと、以下の通りとなります。

 

134 = 3+131 = 7+127 = 31+103 = 37+97 = 61+73 = 67+67 

       = 131+3 = 127+7 = 103+31 = 97+37 = 73+61
      

与えられた数が大きくなると、いくらでも素数の組み合せが見つかるような気がします。しかし、現代数学をもってしてもこの予想を証明することも、反例を作ることもできません(*2)。ちょっと不思議な感じがしますね。

そこで、ゴールドバッハ予想を鑑賞するために、偶数 n を入力とし、和が n となる 2 つの素数の組み合せの数を求めるプログラムを作成してください。

和が n となる素数の組み合せの数とは n = p + q かつ p ≤ q  であるような正の素数 p, q の組み合せの数です。上の例からわかるように和が 134 となる素数の組み合せは6 個です。

(*1)  素数とは、1 または自分自身以外に約数を持たない整数のことである。なお、1 は素数ではない。

(*2)  2007 年 2 月現在、5&times;1017 までの全ての偶数について成り立つことが確かめられている。(Wikipedia)

Input

 複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。 各データセットとして、１つの偶数 n (6 ≤ n ≤ 1000000) が１行に与えられます。

データセットの数は 500 を超えません。

Output

データセット毎に素数の組み合せの数を１行に出力します。

Sample Input

134
4330
34808
98792
0

Output for the Sample Input

6
72
274
607



Sample input:
134
4330
34808
98792
0


Sample output:
6
72
274
607

Submission status: Wrong Answer

Solution code:
import array
import bisect


def is_prime_number(num):
    limit = int(num ** 0.5)

    for lp in range(3, limit + 1, 2):
        if num % lp == 0:
            return False

    return True


def binary_search(num_list, num):
    left = 0
    right = len(num_list) - 1

    while left <= right:
        mid = (left + right) // 2

        if num_list[mid] == num:
            return True
        elif num_list[mid] < num:
            left = mid + 1
        else:
            right = mid - 1

    return False


LENGTH = 1000000
prime_number_list = array.array("i", [True] * (LENGTH + 1))

prime_number_list[0] = False
prime_number_list[1] = False

for lp in range(4, LENGTH + 1, 2):
    prime_number_list[lp] = False

limit = int((LENGTH + 1) ** 0.5)

for lp in range(3, limit + 1, 2):
    if is_prime_number(lp):
        for lp2 in range(lp * 2, LENGTH + 1, lp):
            prime_number_list[lp2] = False

prime_number_list = array.array("i", [index for index, item in enumerate(prime_number_list) if item])

while True:

    input_num = int(input())

    if input_num == 0:
        break

    count = 0

    array_size = bisect.bisect_left(prime_number_list, input_num // 2)

    for lp in prime_number_list[:array_size + 1]:

        search_num = input_num - lp

        if binary_search(prime_number_list, search_num):
            count += 1

    print(count)

Submission status: Wrong Answer

Solution code:
# AOJ 0185 Goldbach's Conjecture II
# Python3 2018.6.20 bal4u

MAX = 1000000
SQRT = 1000     # sqrt(MAX)

prime = [True for i in range(MAX)]
prime[1] = False

def sieve():
	for i in range(3, SQRT, 2):
		if prime[i] is True:
			for j in range(i*i, MAX, i):
				prime[j] = False
sieve()

print(prime[1:20:2])

while True:
	n = int(input())
	if n == 0: break
	i = j = n >> 1
	if (i & 1) == 0:
		i -= 1
		j += 1
	ans = 0
	while i > 0:
		if prime[i] and prime[j]: ans += 1
		i -= 2
		j += 2
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    for line in sys.stdin:
        n = int(line)
        if n == 0:
            break
        else:
            hoge = [i for i in range(2, n)]
            fuga = [2]
            for i in range(1, len(hoge)):
                cnt = 0
                for j in range(i):
                    if hoge[i] % hoge[j] == 0:
                        break
                    else:
                        cnt += 1
                if cnt == i:
                    fuga.append(hoge[i])

            ans = 0
            for i in range(len(fuga) - 1):
                for j in range(i, len(fuga)):
                    if fuga[i] + fuga[j] == n:
                        ans += 1
                    else:
                        pass

            print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
primes = [0, 0] + [1]*999999
for i in range(2, 1001):
    if primes[i]:
        for j in range(i*i, 1000001, i):
            primes[j] = 0

prime_value = [i for i in range(len(primes)) if primes[i]]
while True:
    n = int(input())
    if n == 0:
        break
    x = bisect.bisect_right(prime_value, n//2)
    print(sum(1 for p in prime_value[:x] if primes[n-p]))

Submission status: Accepted

Solution code:
# Aizu Problem 0185: Goldbach Conjecture II
#
import sys, math, os, bisect

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def primes2(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1,int(n**0.5)//3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
        sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]

primes = primes2(10**6)
pset = set(primes)

while True:
    n = int(input())
    if n == 0:
        break
    S = 0
    for p in primes:
        if p > n // 2:
            break
        if n - p in pset:
            S += 1
    print(S)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0185

"""
import sys
from sys import stdin
from bisect import bisect_left
input = stdin.readline


def create_prime_list(limit):
    """ ??¨??????????????????????????§limit?????§????´???°?????????????±???????
    https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
    """
    x = limit**0.5
    primes = []
    nums = [x for x in range(2, limit+1)]
    while nums[0] <= x:
        primes.append(nums[0])
        current_prime = nums[0]
        nums = [x for x in nums if x % current_prime != 0]
    primes.extend(nums)
    return primes


def main(args):
    primes = create_prime_list(1000000)

    while True:
        n = int(input())
        if n == 0:
            break

        ans = 0                 #  ????????????????????????????????°
        for i in range(n):
            a = primes[i]
            if a > n/2:
                break
            i = bisect_left(primes, n - a)
            if i != len(primes) and primes[i] == n-a:
                ans += 1
        print(ans)



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import array


def is_prime_number(num):
    limit = int(num ** 0.5)

    for lp in range(3, limit + 1, 2):
        if num % lp == 0:
            return False

    return True


LENGTH = 1000000
prime_number_list = array.array("i", [True] * (LENGTH + 1))

prime_number_list[0] = False
prime_number_list[1] = False

for lp in range(4, LENGTH + 1, 2):
    prime_number_list[lp] = False

limit = int((LENGTH + 1) ** 0.5)

for lp in range(3, limit + 1, 2):
    if is_prime_number(lp):
        for lp2 in range(lp * 2, LENGTH + 1, lp):
            prime_number_list[lp2] = False

while True:
    input_num = int(input())

    if input_num == 0:
        break

    count = 0

    for lp in range(2, input_num // 2 + 1):

        if prime_number_list[lp] and prime_number_list[input_num - lp]:
            count += 1

    print(count)

Submission status: Accepted

Solution code:
MAX = 1000001
primes = list()
for i in range(MAX):
    primes.append(True)
primes[0] = False
primes[1] = False

for i in range(2, MAX):
    j = i + i
    while j < MAX:
        primes[j] = False
        j = j + i

while True:
    n = int(input())
    if n == 0:
        break

    ans = 0
    for i in range(1, n // 2 + 1):
        if primes[i] and primes[n-i]:
            ans += 1
    print(ans)

Submission status: Accepted

Solution code:
# AOJ 0185 Goldbach's Conjecture II
# Python3 2018.6.20 bal4u

MAX = 1000000
SQRT = 1000     # sqrt(MAX)

prime = [True for i in range(MAX)]
prime[1] = False

def sieve():
	for i in range(3, SQRT, 2):
		if prime[i] is True:
			for j in range(i*i, MAX, i):
				prime[j] = False
sieve()

while True:
	n = int(input())
	if n == 0: break
	i = j = n >> 1
	if (i & 1) == 0:
		i -= 1
		j += 1
	ans = 0
	while i > 0:
		if prime[i] and prime[j]: ans += 1
		i -= 2
		j += 2
	print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
def primes(n):
  tf = [True] * (n + 1)
  tf[0] = tf[1] = False
  for i in range(2, int(n ** (1 / 2) + 1)):
    if tf[i]:
      for j in range(i ** 2, n + 1, i):
        tf[j] = False
  return [i for i in range(n + 1) if tf[i]]

def search_pair(x, prime_lst, len_prime):
  cnt = 0
  for prime in prime_lst:
    if prime > x // 2:
      break
    i = bl(prime_lst, x - prime)
    if i < len_prime and prime_lst[i] == x - prime:
      cnt += 1
  return cnt

prime_lst = primes(1000000)
len_prime = len(prime_lst)

while True:
  n = int(input())
  if n == 0:
    break
  print(search_pair(n, prime_lst, len_prime))

Submission status: Accepted

Solution code:
import math
N=1000000
prime=[1]*(N+1)
prime[0],prime[1]=0,0
for i in range(2,int(math.sqrt(N))):
    if prime[i]==1:
        j=i
        while i*j<=N:
            prime[i*j]=0
            j+=1

while True:
    n=input()
    if n==0:break
    cnt=0
    for i in range(2,n/2+1):
        if prime[i]==1:
            if prime[n-i]==1:
                cnt+=1
    print cnt

Submission status: Accepted

Solution code:
from itertools import compress
MAXN = 1000001
p = [True]*MAXN
p[0] = p[1] = False
for i in xrange(int(MAXN**0.5)+1):
    if p[i]:
        for j in xrange(i+i,MAXN,i):
            p[j] = False
while True:
    n = input()
    if n == 0:
        break
    print sum(1 for i in compress(xrange(n/2+1),p) if p[n-i])

Submission status: Accepted

Solution code:
r = 1000000
sqrt = int(r**0.5)
p = [1]*r
p[0] = 0
p[3::2] = [0 for x in range(3,r,2)]
for i in range(2,sqrt):
	if p[i]:
		p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]

while 1:
	n = int(raw_input())
	if n == 0: break
	ans = 0
	for i in range(2,n/2+1):
		if p[i-1] and p[n-i-1]:
			ans += 1
	print ans

Submission status: Accepted

Solution code:
MN = 1000000
prime = []
mem = [False] * 2 + [True] * MN
for i in range(2, MN):
  if not mem[i]:
    continue
  prime.append(i)
  for j in range(i + i, MN, i):
    mem[j] = False

while True:
  N, ans = input(), 0
  if not N:
    break

  for p in prime:
    if p > N / 2:
      break
    if mem[N - p]:
      ans += 1
  print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

M = 1000000
sq = int(M**.5)
pl = []
p = [1]*(M+1)
p[0] = p[1] = 0
for x in range(2, sq+1):
    if p[x]:
        for y in range(x*x, M+1, x):
            p[y] = 0
        pl.append(x)
for x in range(sq+1, M+1):
    if p[x]:
        pl.append(x)

def solve():
    N = int(readline())
    if N == 0:
        return False
    ans = 0
    N2 = N//2
    for x in pl:
        if N2 < x:
            break
        if p[N-x]:
            ans += 1
    write("%d\n" % ans)
    return True
while solve():
    ...

Submission status: Runtime Error

Solution code:
while True:
    m = input()
    if m == 0: break
    L = [i for i in range(2, m+1)]
    p = 2
    q = None
    ans = []
    while L:
        _L = L[:]
        for n in _L:
            if n == p:
                ans.append(n)
                L.remove(n)
            else:
                if n % p == 0:
                    L.remove(n)
                    c = 1
                elif q is None:
                    q = n
        else:
            p = q
            q = None
    c = 0
    while ans:
        b = ans[0]
        for n in sorted(ans, reverse=True):
            if b+n == m:
                c += 1
                ans.remove(n)
                del ans[0]
                break
            elif b+n < m:
                del ans[0]
                break
        else:
            break
    print c

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0185

"""
import sys
from sys import stdin
from bisect import bisect_left
input = stdin.readline


def create_prime_list(limit):
    """ ??¨??????????????????????????§limit?????§????´???°?????????????±???????
    https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
    """
    x = limit**0.5
    primes = []
    nums = [x for x in range(2, limit+1)]
    while nums[0] <= x:
        primes.append(nums[0])
        current_prime = nums[0]
        nums = [x for x in nums if x % current_prime != 0]
    primes.extend(nums)
    return primes


def main(args):
    primes = create_prime_list(500000)

    while True:
        # n = 98792
        n = int(input())
        if n == 0:
            break

        ans = 0                 #  ????????????????????????????????°
        for i in range(n):
            a = primes[i]
            if a > n/2:
                break
            i = bisect_left(primes, n - a)
            if i != len(primes) and primes[i] == n-a:
                ans += 1
        print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Runtime Error

Solution code:
import array
import bisect


def is_prime_number(num):
    limit = int(num ** 0.5)

    for lp in range(3, limit + 1, 2):
        if num % lp == 0:
            return False

    return True


LENGTH = 1000000
prime_number_list = array.array("i", [True] * (LENGTH + 1))

prime_number_list[0] = False
prime_number_list[1] = False

for lp in range(4, LENGTH + 1, 2):
    prime_number_list[lp] = False

limit = int((LENGTH + 1) ** 0.5)

for lp in range(3, limit + 1, 2):
    if is_prime_number(lp):
        for lp2 in range(lp * 2, LENGTH + 1, lp):
            prime_number_list[lp2] = False

prime_number_list = array.array("i", [index for index, item in enumerate(prime_number_list) if item])

while True:

    input_num = int(input())

    if input_num == 0:
        break

    count = 0

    array_size = bisect.bisect_left(prime_number_list, input_num // 2)

    for lp in prime_number_list[:array_size + 1]:

        search_num = input_num - lp

        index = bisect.bisect_left(prime_number_list, search_num)

        if prime_number_list[index] == search_num:
            count += 1

    print(count)

Submission status: Runtime Error

Solution code:
import array
import bisect


def is_prime_number(num):
    limit = int(num ** 0.5)

    for lp in range(3, limit + 1, 2):
        if num % lp == 0:
            return False

    return True


def binary_search(num_list, num):
    left = 0
    right = len(num_list)

    while left <= right:
        mid = (left + right) // 2

        if num_list[mid] == num:
            return True
        elif num_list[mid] < num:
            left = mid + 1
        else:
            right = mid - 1

    return False


LENGTH = 1000000
prime_number_list = array.array("i", [True] * (LENGTH + 1))

prime_number_list[0] = False
prime_number_list[1] = False

for lp in range(4, LENGTH + 1, 2):
    prime_number_list[lp] = False

limit = int((LENGTH + 1) ** 0.5)

for lp in range(3, limit + 1, 2):
    if is_prime_number(lp):
        for lp2 in range(lp * 2, LENGTH + 1, lp):
            prime_number_list[lp2] = False

prime_number_list = array.array("i", [index for index, item in enumerate(prime_number_list) if item])

while True:

    input_num = int(input())

    if input_num == 0:
        break

    count = 0

    array_size = bisect.bisect_left(prime_number_list, input_num // 2)

    for lp in prime_number_list[:array_size + 1]:

        search_num = input_num - lp

        if binary_search(prime_number_list, search_num):
            count += 1

    print(count)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as bl
def primes(n):
  tf = [True] * (n + 1)
  tf[0] = tf[1] = False
  for i in range(2, int(n ** (1 / 2) + 1)):
    if tf[i]:
      for j in range(i ** 2, n + 1, i):
        tf[j] = False
  return [i for i in range(n + 1) if tf[i]]

def search_pair(x, prime_lst):
  cnt = 0
  for prime in prime_lst:
    if prime > x // 2:
      break
    i = bl(prime_lst, x - prime)
    if prime_lst[i] == x - prime:
      cnt += 1
  return cnt

prime_lst = primes(1000000)

while True:
  n = int(input())
  if n == 0:
    break
  print(search_pair(n, prime_lst))

Submission status: Runtime Error

Solution code:
MN = 100000
prime = []
mem = [False] * 2 + [True] * MN
for i in range(2, MN):
  if not mem[i]:
    continue
  prime.append(i)
  for j in range(i + i, MN, i):
    mem[j] = False

while True:
  N, ans = input(), 0
  if not N:
    break

  for p in prime:
    if p > N / 2:
      break
    if mem[N - p]:
      ans += 1
  print(ans)