Problem:


ゴールドバッハの予想

4 以上の偶数は 2 つの素数の和で表すことができるということが知られています。これはゴールドバッハ予想といい、コンピュータの計算によりかなり大きな数まで正しいことが確かめられています。例えば、10 は、7 + 3、5 + 5 の 2 通りの素数の和で表すことができます。

整数 n を入力し、n を 2 つの素数の和で表す組み合わせ数が何通りあるかを出力するプログラムを作成してください。ただし、n は 4 以上、50,000 以下とします。また、入力される n は偶数であるとはかぎりません。

Input

複数のデータセットが与えられます。各データセットに n が１行に与えられます。n が 0 のとき入力の最後とします。データセットの数は 10,000 を超えません。

Output

各データセットに対して、n を 2 つの素数の和で表す組み合わせ数を１行に出力して下さい。

Sample Input

10
11
0

Output for the Sample Input

2
0



Sample input:
10
11
0


Sample output:
2
0

Submission status: Time Limit Exceeded

Solution code:

import sys


def solv(n):
    r = 0
    if n % 2 == 1:
        if (n-2) in primes:
            return 1
    else:
        for p in primes:
            if n/2 < p:
                break
            q = n - p
            if q in primes:
                r += 1
    return r


def prime_list(n):
    limit = int(n ** 0.5) + 1
    lis = range(1, n + 1, 2)
    lis[0] = 2
    while True:
        if len(lis) == 0:
            break
        p = lis.pop(0)
        yield p
        if p <= limit:
            lis = [x for x in lis if x % p != 0]


primes = []
for p in prime_list(50000):
    primes.append(p)

while True:
    n = int(sys.stdin.readline())
    if n == 0:
        exit()
    print solv(n)

Submission status: Time Limit Exceeded

Solution code:

import sys


def solv(n):
    r = 0
    if n % 2 == 1:
        if (n-2) in primes:
            r = 1
    else:
        for p in primes:
            if n/2 < p:
                break
            q = n - p
#            if q in primes:
            if binary_search(primes, q):
                r += 1
    return r


def prime_list(n):
    limit = int(n ** 0.5) + 1
    lis = range(1, n + 1, 2)
    lis[0] = 2
    while True:
        if len(lis) == 0:
            break
        p = lis.pop(0)
        yield p
        if p <= limit:
            lis = [x for x in lis if x % p != 0]


def binary_search(lis, x):
    if len(lis) == 0:
        return None
    i = len(lis) / 2
    if lis[i] == x:
        return x
    elif x < lis[i]:
        return binary_search(lis[:i], x)
    else:
        return binary_search(lis[i+1:], x)


primes = []
for p in prime_list(50000):
    primes.append(p)

while True:
    n = int(sys.stdin.readline())
    if n == 0:
        exit()
    print solv(n)

Submission status: Time Limit Exceeded

Solution code:

import sys


def solv(n):
    r = 0
    if n % 2 == 1:
#        if (n-2) in primes:
        if binary_search(primes, n-2):
            r = 1
    else:
        for p in primes:
            if n/2 < p:
                break
            q = n - p
#            if q in primes:
            if binary_search(primes, q):
                r += 1
    return r


def prime_list(n):
    limit = int(n ** 0.5) + 1
    lis = range(1, n + 1, 2)
    lis[0] = 2
    while True:
        if len(lis) == 0:
            break
        p = lis.pop(0)
        yield p
        if p <= limit:
            lis = [x for x in lis if x % p != 0]


def binary_search(lis, x):
    if len(lis) == 0:
        return None
    i = len(lis) / 2
    if lis[i] == x:
        return x
    elif x < lis[i]:
        return binary_search(lis[:i], x)
    else:
        return binary_search(lis[i+1:], x)


primes = []
for p in prime_list(50000):
    primes.append(p)

while True:
    n = int(sys.stdin.readline())
    if n == 0:
        exit()
    print solv(n)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin
from itertools import combinations_with_replacement

L = range(2, 50000)
P = []
while L[0] ** 2 < 50000:
    P.append(L[0])
    L = [i for i in L if i % P[-1]]
P.extend(L)
del L

for line in stdin:
    if line.startswith('0'):
        break
    n = int(line)
    cnt = 0
    for a, b in combinations_with_replacement(P, 2):
        if a >= n:
            break
        if a + b == n:
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin
from itertools import combinations_with_replacement

L = range(2, 50000)
P = []
while L[0] ** 2 < 50000:
    P.append(L[0])
    L = [i for i in L if i % P[-1]]
P.extend(L)
del L

for line in stdin:
    if line.startswith('0'):
        break
    n = int(line)
    cnt = 0
    if n % 2 or not (n in P):
        for a, b in combinations_with_replacement(P, 2):
            if a >= n:
                break
            if a + b == n:
                cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin
from itertools import combinations_with_replacement

def enum_prime(m):
    L = range(2, m)
    P = []
    while L[0] ** 2 < m:
        P.append(L[0])
        L = [i for i in L if i % P[-1]]
    return P + L

P1 = enum_prime(50000)
P2 = P1[:]

for line in stdin:
    if line.startswith('0'):
        break
    n = int(line)
    cnt = 0
    if n % 2 == 0:
        for a in P1:
            if a + a == n:
                cnt += 1
                break
            for b in P2:
                if b < a:
                    continue
                if a + b == n:
                    cnt += 1
                    break
                if a + b > n:
                    break
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin

def enum_prime(m):
    L = range(2, m)
    P = []
    while L[0] ** 2 < m:
        P.append(L[0])
        L = [i for i in L if i % P[-1]]
    return P + L

P = enum_prime(50000)
length = len(P)

for line in stdin:
    if line.startswith('0'):
        break
    n = int(line)
    cnt = 0
    if (n - 2) in P:
        cnt = 1
    elif n % 2 == 0:
        for i in xrange(length):
            for j in xrange(i, length):
                s = P[i] + P[j]
                if s >= n:
                    if s == n:
                        cnt += 1
                    break
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin

def enum_prime(m):
    L = range(2, m)
    P = []
    while L[0] ** 2 < m:
        P.append(L[0])
        L = [i for i in L if i % P[-1]]
    return P + L

P = enum_prime(50000)

for line in stdin:
    if line.startswith('0'):
        break
    n = int(line)
    cnt = 0
    if n % 2 == 0:
        for p in P:
            if (n - p) in P:
                cnt += 1
            elif p + p > n:
                break
    elif (n - 2) in P:
        cnt = 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin

def enum_prime(m):
    L = [True for _ in xrange(m + 1)]
    L[0] = L[1] = False

    for i in xrange(2, m + 1):
        if not L[i]:
            continue
        for j in xrange(i + i, m + 1, i):
            L[j] = False
        if m < i * i:
            break
    return L

P = enum_prime(50000)

for line in stdin:
    if line.startswith('0'):
        break
    n = int(line)
    cnt = 0
    if n % 2 == 0:
        for p, isprime in enumerate(P):
            if not isprime:
                continue
            if p + p > n:
                break
            if P[n - p]:
                cnt += 1
    elif P[n - 2]:
        cnt = 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
p = [True] * (50000)
p[0] = p[1] = False
for i in range(2, len(p)):
    if p[i]:
        for j in range(i * 2, len(p), i):
            p[j] = False

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def sieve(m):
    N=range(1,m+2,2)
    r=int(m**.5)
    h=len(N)
    N[0]=0
    for i in range(h):
        x=N[i]
        if x>r: break
        if x and i+x<h: N[i+x:h:x]=[0] * ((h-1-i-x)/x+1)
    return N
def f0056(n):
    x=0
    if n%2==1:
        if SIEVES[(n-2)/2]!=0: x=1
    else:
        x=len([e for e in SIEVES if 0<e<=n/2 and SIEVES[(n-e)/2]!=0])
    return x
        
SIEVES=sieve(50000)
for n in sys.stdin:
    n=int(n)
    if n==0: break
    print f0056(n)

Submission status: Time Limit Exceeded

Solution code:
import sys
def sieve(m):
    N=range(1,m+2,2)
    r=int(m**.5)
    h=len(N)
    N[0]=0
    for i in range(h):
        x=N[i]
        if x>r: break
        if x and i+x<h: N[i+x:h:x]=[0] * ((h-1-i-x)/x+1)
    return N
def f0056(n):
    x=0
    b=n/2
    if n==2 or n==3: return 1
    if n%2==1:
        if n-2 in PRIMES: x=1
    else:
        for e in PRIMES:
            if e>b:break
            if n-e in PRIMES: x+=1
    return x
        
SIEVES=sieve(50000)
PRIMES=filter(None,[2]+SIEVES)
for n in sys.stdin:
    n=int(n)
    if n==0: break
    print f0056(n)

Submission status: Time Limit Exceeded

Solution code:
import math

r = 50001
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]

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

Submission status: Time Limit Exceeded

Solution code:
import math

r = 50001
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]

prime = []
for i in range(len(p)):
    if p[i] == 1:
        prime.append(i+1)

while True:
    n = int(raw_input())
    if n == 0:
        break
    count = 0
    for i in prime:
        if i > n/2:
            break
        m = n - i
        if prime.count(m) == 1:
                count += 1
    print count

Submission status: Time Limit Exceeded

Solution code:
import math
 
r = 50001
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]
 
while True:
    n = int(raw_input())
    if n == 0:
        break
    count = 0
    m = n/2
    for i in range(m):
        if p[i] == 1 and p[m-i-1] == 1:
            count += 1

Submission status: Time Limit Exceeded

Solution code:
from itertools import *

def sieve(n):
    a = range(n)
    a[:2] = None, None
    for i in range(2, n):
        if i ** 2 >= n: break
        if not a[i]: continue
        for i in range(i ** 2, n, i):
            a[i] = None
    return [v for v in a if v]

def isPrime(p):
    if p < 2:
        return False
    for i in count(2):
        if i * i > p:
            return True
        if p % i == 0:
            return False

a = sieve(50000)
while True:
    n = int(raw_input())
    if n == 0: break
    if n % 2 == 1:
        print 0
        continue
    ct = 0
    for v in a:
        if v > n / 2: break
        if isPrime(n - v):
            ct += 1
    print ct

Submission status: Time Limit Exceeded

Solution code:
N = 50000
t = [1]*N
p = []
for i in range(3, N + 1, 2):
    if t[i]:
        p.append(i)
        for j in range(3*i, N+1, 2*i): t[j] = 0

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

    if n % 2:
        print(1 if n - 2 in p else 0)
    else:
        count = 0
        for p1 in p:
            if 2*p1 > n: break
            if n - p1 in p: count += 1
        print(count)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right
from itertools import chain, compress

ub = 50000
is_prime = [0, 0, 1, 1] + [0]*(ub-3)
is_prime[5::6] = is_prime[7::6] = [1]*int(ub/6)
primes = [2, 3]
append = primes.append

for n in chain(range(5, ub, 6), range(7, ub, 6)):
    if is_prime[n]:
        append(n)
        is_prime[n*3::n*2] = [0]*((ub-n)//(n*2))
primes.sort()

for n in map(int, sys.stdin):
    if not n:
        break
    if n%2:
        print(is_prime[n-2])
    else:
        print(len([1 for p in primes[:bisect_right(primes, n/2)] if is_prime[n-p]]))

Submission status: Accepted

Solution code:
from itertools import *
import sys

maxnum = 50001
primes = [True]*maxnum
primes[0] = primes[1] = False
for i in xrange(maxnum):
    if i >= maxnum**0.5 : break
    if not primes[i]: continue
    for j in xrange(i*2,maxnum,i): primes[j] = False

p = [ i for i in xrange(maxnum) if primes[i] ]
c = [0]*maxnum*2
for i,j in combinations_with_replacement(p,2):
    c[i+j] += 1

for s in sys.stdin:
    d = int(s)
    if d == 0: break
    print c[d]

Submission status: Accepted

Solution code:
import sys
f = sys.stdin

def create_prime(n):
    prime = [1] * (n + 1)
    prime[:2] = [0, 0]
    for i in range(len(prime)):
        if prime[i]:
            for j in range(2 * i, len(prime), i):
                prime[j] = 0
    return prime

sieve = create_prime(50000)

prime = []
for i in range(25001):
    if sieve[i]:
        prime.append(i)

while True:
    n = int(f.readline())
    if n == 0:
        break
    cnt = 0
    temp = n // 2
    for i in prime:
        if i > temp:
            break
        if sieve[n - i]:
            cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
def pri(t):
    i=2
    while i**2<=t:
        if t%i==0:
            return 0
        i=i+1
    return 1

l=[]
for i in range(2,50000):
    if pri(i):
        l.append(i)
s=5133
ans={}
for i in range(5132):
    for j in range(i,5133):
        a,b=l[i],l[j]
        if a+b>50000:
            break
        if ans.has_key(a+b):
            ans[a+b]+=1
        else:
            ans[a+b]=1
while 1:
    n=int(raw_input())
    if n==0:
        break
    print ans[n] if ans.has_key(n) else 0

Submission status: Accepted

Solution code:
from math import sqrt, floor

p = [2]
for i in range(3, 50000, 2):
    for j in range(3, floor(sqrt(i)) + 1, 2):
        if not i % j:
            break
    else:
        p.append(i)
sp = set(p)

while True:
    n = int(input())
    if not n:
        break
    if n & 1:
        print(int(n - 2 in sp))
        continue
    n2 = n // 2
    cnt = 0
    for i in p:
        if n2 < i:
            break
        if n - i in sp:
            cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
def make_tbl(n):
    tbl = [False, True, False, False, False, True] * (n // 6 + 1)
    for i in range(1, 4):
        tbl[i] = not tbl[i]
    p, stp, sqrt = 5, 2, n ** 0.5
    while p < sqrt:
        for i in range(p ** 2, n, 2 * p):
            tbl[i] = False
        while True:
            p += stp
            stp = 6 - stp
            if tbl[p]:
                break
    return tbl
tbl = make_tbl(50000)
ps = [i for i in range(50000) if tbl[i]]
while True:
    n = int(input())
    if not n:
        break
    res = 0
    if n % 2:
        if tbl[n - 2]:
            res += 1
    else:
        res = 0
        for p in ps:
            if 2 * p > n:
                break
            if tbl[n - p]:
                res += 1
    print(res)

Submission status: Accepted

Solution code:
def primes(n):
  l = [1 for i in range(n+1)]
  l[0] = l[1] = 0
  for i in range(2,int((n)**(1/2))+1):
    if l[i] == 1:
      for j in range(2,n//i+1):
        l[i*j] = 0
  return l

l = primes(50000)
while True:
  n = int(input())
  if n == 0:
    break
  count = 0
  if not(n%2):
    for i in range(3,n//2+1,2):
      if (l[i] and l[n-i]):
        count += 1
    if n == 4:
      count = 1
  else:
    if l[n-2]:
      count += 1
  print(count)

Submission status: Accepted

Solution code:
# aoj0056.py

LIM = 50001

# prepare primes

is_prime = [True for _ in range(LIM)]

is_prime[0] = is_prime[1] = False

# sieve of eratosthenes
for x in range(LIM//2 + 1):
    if is_prime[x]:
        for y in range(x*x, LIM, x):
            is_prime[y] = False

primes = [x for x in range(LIM) if is_prime[x]]

# END `prepare primes`

count_arr = [0 for x in range(LIM)]

len_primes = len(primes)

for x in range(len_primes):
    p = primes[x]
    for y in range(x, len_primes):
        q = primes[y]
        if p+q >= LIM:
            break
        count_arr[p+q] += 1

while True:
    n = int(input())
    if n == 0:
        break
    print(count_arr[n])

Submission status: Accepted

Solution code:
pr = [True] * 50001
for i in range(2,225):
    if pr[i]:
        for j in range(i * 2, 50001, i):
            pr[j] = False

prime = [2] + [i for i in range(3, 50001, 2) if pr[i]]

def gold_count(n):
    res = 0
    for i in prime:
        if i > n // 2:
            break
        if pr[n - i]:
            res += 1
    return res

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

Submission status: Accepted

Solution code:
pr = [True] * 50001
for i in range(2,225):
    if pr[i]:
        for j in range(i * 2, 50001, i):
            pr[j] = False

prime = [2] + [i for i in range(3, 50001, 2) if pr[i]]

def gold_count(n):
    res = 0
    if pr[n - 2]:
        res += 1
    for i in range(3, n // 2 + 1, 2):
        if pr[i] and pr[n - i]:
            res += 1
    return res

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

Submission status: Accepted

Solution code:
pr = [True] * 50001
for i in range(2,225):
    if pr[i]:
        for j in range(i * 2, 50001, i):
            pr[j] = False

def gold_count(n):
    res = 0
    if pr[n - 2]:
        res += 1
    for i in range(3, n // 2 + 1, 2):
        if pr[i] and pr[n - i]:
            res += 1
    return res

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

Submission status: Accepted

Solution code:
import bisect
primes = [0,0] + [1]*49999
for i in range(2, 224):
    if primes[i]:
        for j in range(i*i, 50001, i):
            primes[j] = 0

values = [k for k, b in enumerate(primes) if b]
while True:
    n = int(input())
    if n == 0:
        break
    end = bisect.bisect_right(values, n//2)
    print(sum(1 for i in values[:end] if primes[n-i]))

Submission status: Accepted

Solution code:
isPrime = []
prime = []
count = []

def init():
    for i in range(50000 + 1):
        isPrime.append(True)
        count.append(0)

def eratos():
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, int((50000 ** (1 / 2))) + 1):
        if (isPrime[i]):
            for j in range(i * 2, 50000 + 1, i):
                isPrime[j] = False
    
    for i in range(2, 50001):
        if isPrime[i]:
            prime.append(i)


def table():
    for i in prime:
        for j in prime:
            if i < j:
                continue
            if i + j > 50000:
                continue
            count[i + j] += 1

init()
eratos()
table()

while True:
    n = int(input())
    if n == 0:
        break
    print(count[n])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0056
"""
from math import sqrt, ceil, pow
import bisect


# https://github.com/mccricardo/sieve_of_atkin/blob/master/sieve_of_atkin.py
class SieveOfAtkin:
    def __init__(self, limit):
        self.limit = limit
        self.primes = []
        self.sieve = [False] * (self.limit + 1)

    def flip(self, prime):
        try:
            self.sieve[prime] = True if self.sieve[prime] == False else False
        except KeyError:
            pass

    def invalidate(self, prime):
        try:
            if self.sieve[prime] == True: self.sieve[prime] = False
        except KeyError:
            pass

    def isPrime(self, prime):
        try:
            return self.sieve[prime]
        except KeyError:
            return False

    def getPrimes(self):
        testingLimit = int(ceil(sqrt(self.limit)))

        for i in range(testingLimit):
            for j in range(testingLimit):
                # n = 4*i^2 + j^2
                n = 4 * int(pow(i, 2)) + int(pow(j, 2))
                if n <= self.limit and (n % 12 == 1 or n % 12 == 5):
                    self.flip(n)

                # n = 3*i^2 + j^2
                n = 3 * int(pow(i, 2)) + int(pow(j, 2))
                if n <= self.limit and n % 12 == 7:
                    self.flip(n)

                # n = 3*i^2 - j^2
                n = 3 * int(pow(i, 2)) - int(pow(j, 2))
                if n <= self.limit and i > j and n % 12 == 11:
                    self.flip(n)

        for i in range(5, testingLimit):
            if self.isPrime(i):
                k = int(pow(i, 2))
                for j in range(k, self.limit, k):
                    self.invalidate(j)

        self.primes = [2, 3] + [x for x in range(len(self.sieve)) if self.isPrime(x) and x >= 5]
        return self.primes




def solve1(num, primes):
    # 6.94[s]
    result = 0

    # list_primes = [x for x in primes if x < num]
    i = bisect.bisect_left(primes, num)
    list_primes = primes[:i]


    set_primes = set(list_primes)
    for x in list_primes:
        if x > num/2:
            break
        if (num-x) in set_primes:
            # print('solve1: {} + {} = {}'.format(x, num-x, num))
            result += 1
    return result


def solve2(num, primes):
    result = 0
    sub_primes = set(x for x in primes if x < num)
    while sub_primes:
        x = sub_primes.pop()
        if x*2 == num:
            result += 1
        elif (num-x) in sub_primes:
            result += 1
            sub_primes.remove(num-x)
    return result



def solve3(num, primes):
    # 17.96[s]
    result = 0
    sub_primes = [x for x in primes if x < num]
    primes_len = len(sub_primes)
    # print('solve3: primes_len: {}'.format(primes_len))
    # print(sub_primes)

    n = 0
    while True:
        if sub_primes[n] > num/2:
            break
        i = bisect.bisect_left(sub_primes, num-sub_primes[n])
        if i != primes_len and sub_primes[i] == num-sub_primes[n]:
            # print('solve3: {} + {} = {}'.format(sub_primes[n], num-sub_primes[n], num))
            result += 1
        n += 1
    return result



if __name__ == '__main__':
    A = SieveOfAtkin(50000)
    A.getPrimes()
    while True:
        num = int(input())
        if num == 0:
            break

        # ????????¨???????????¨???
        result = solve1(num, A.primes)
        print(result)

Submission status: Accepted

Solution code:
import bisect
primes = [0, 0] + [1] * 49999
for i in range(2, 225):
    if primes[i]:
        for j in range(i*i, 50001, i):
            primes[j] = 0
values = [i for i, k in enumerate(primes) if k]
while True:
    n = int(input())
    if n == 0:
        break
    I = bisect.bisect(values, n//2)
    print(sum(primes[n-i] for i in values[:I]))

Submission status: Accepted

Solution code:
# Aizu Problem 0056: Goldbach's Conjecture
#
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(50000)
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:
import bisect
primes = [0, 0] + [1] * 49999
for i in range(2, 225):
    if primes[i]:
        for j in range(i*i, 50001, i):
            primes[j] = 0
values = [i for i, k in enumerate(primes) if k]
while True:
    n = int(input())
    if n == 0:
        break
    I = bisect.bisect(values, n//2)
    print(sum(primes[n-v] for v in values[:I]))

Submission status: Accepted

Solution code:
import bisect
primes = [0, 0] + [1] * 49999
for i in range(2, 225):
    if primes[i]:
        for j in range(i*i, 50001, i):
            primes[j] = 0
values = [i for i, k in enumerate(primes) if k]
while True:
    n = int(input())
    if n == 0:
        break
    I = bisect.bisect(values, n//2)
    print(sum(1 for v in values[:I] if primes[n-v]))

Submission status: Accepted

Solution code:
import bisect
primes = [0, 0] + [1] * 49999
for i in range(2, 224):
    if primes[i]:
        for j in range(i*i, 50001, i):
            primes[j] = 0
values = [i for i, k in enumerate(primes) if k]
while True:
    n = int(input())
    if n == 0:
        break
    I = bisect.bisect(values, n//2)
    print(sum(1 for v in values[:I] if primes[n-v]))

Submission status: Accepted

Solution code:
import bisect
primes = [0, 0] + [1] * 49999
for i in range(2, 224):
    if primes[i]:
        for j in range(i*i, 50001, i):
            primes[j] = 0
values = [i for i, k in enumerate(primes) if k]
while True:
    n = int(input())
    if n == 0:
        break
    I = bisect.bisect(values, n//2)
    print(len([1 for v in values[:I] if primes[n-v]]))

Submission status: Accepted

Solution code:
n = 50001
is_prime = [i for i in range(n)]
is_prime[0] = is_prime[1] = 0
i = 2
while i**2 <= n:
    j = i*2
    while j < n:
        is_prime[j] = 0
        j += i
    i += 1

prime_set  = set(is_prime)
prime_set.remove(0)
prime_list = sorted(list(prime_set))

while True:
    cnt = 0
    n = int(input())
    if n == 0:
        break
    for i in prime_list:
        if i > n//2:
            break
        if n - i in prime_set:
            cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
import bisect
primes = [0, 0] + [1] * 49999
for i in range(2, 224):
    if primes[i]:
        for j in range(i*i, 50001, i):
            primes[j] = 0
values = [i for i, k in enumerate(primes) if k]
while True:
    n = int(input())
    if n == 0:
        break
    I = bisect.bisect(values, n//2)
    print(len([1 for v in values[:I] if primes[n-v]]))

Submission status: Accepted

Solution code:
import bisect
from itertools import *
n=range(50001);a=list(n);a[1]=0
for i in range(2,224):a[i*2::i]=[0]*len(a[i*2::i])
p=list(compress(n,a))
for x in iter(input,'0'):x=int(x);print(sum(a[x-d]>0 for d in p[:bisect.bisect(p,x//2)]))

Submission status: Accepted

Solution code:
import bisect
from itertools import *
n=range(50001);a=list(n);a[1]=0
for i in range(2,224):a[i*2::i]=[0]*len(a[i*2::i])
p=list(compress(n,a))
for x in iter(input,'0'):x=int(x);print(sum(1 for d in p[:bisect.bisect(p,x//2)]if a[x-d]))

Submission status: Accepted

Solution code:
from bisect import *
from itertools import *
n=range(50001);a=list(n);a[1]=0
for i in range(2,224):a[i*2::i]=[0]*len(a[i*2::i])
p=list(compress(n,a))
for x in iter(input,'0'):x=int(x);print(sum(1 for d in p[:bisect(p,x//2)]if a[x-d]))

Submission status: Accepted

Solution code:
import bisect,sys
from itertools import *
n=range(50001);a=list(n);a[1]=0
for i in range(2,224):a[i*2::i]=[0]*len(a[i*2::i])
p=list(compress(n,a))
for x in sys.stdin:
 x=int(x)
 if x:print(sum(1 for d in p[:bisect.bisect(p,x//2)]if a[x-d]))

Submission status: Accepted

Solution code:
import bisect,sys
from itertools import *
n=range(50001);a=list(n);a[1]=0
for i in range(2,224):a[i*2::i]=[0]*len(a[i*2::i])
p=list(compress(n,a))
for x in map(int,sys.stdin):
 if x:print(sum(1 for d in p[:bisect.bisect(p,x//2)]if a[x-d]))

Submission status: Accepted

Solution code:
import bisect,sys
from itertools import *
n=range(50001);a=list(n);a[1]=0
for i in range(2,224):a[i*2::i]=[0]*len(a[i*2::i])
for x in map(int,sys.stdin):
 if x:print(sum(1 for d in compress(n[:x//2+1],a[:x//2+1])if a[x-d]))

Submission status: Accepted

Solution code:
import bisect,sys
from itertools import *
n=range(50001);a=list(n);a[1]=0
for i in range(2,224):a[i*2::i]=[0]*len(a[i*2::i])
p=list(compress(n,a))
for x in map(int,sys.stdin):
 if x:print(len([1 for d in p[:bisect.bisect(p,x//2)]if a[x-d]]))

Submission status: Accepted

Solution code:
MAX = 50001

is_prime = [True for _ in range(MAX)]
is_prime[0] = is_prime[1] = False
for i in range(2, int(MAX ** (1 / 2)) + 1):
  if is_prime[i]:
    for j in range(i ** 2, MAX, i):
      is_prime[j] = False

primes = [i for i in range(MAX) if is_prime[i]]

while True:
  n = int(input())
  if not n:
    break
  
  ans = 0
  for i in primes:
    if i > n // 2:
      break
    if is_prime[n - i]:
      ans += 1

  print(ans)

Submission status: Accepted

Solution code:
MAX = 50001

is_prime = [True for _ in range(MAX)]
is_prime[0] = is_prime[1] = False
for i in range(2, int(MAX ** (1 / 2)) + 1):
  if is_prime[i]:
    for j in range(i ** 2, MAX, i):
      is_prime[j] = False

primes = [i for i in range(MAX) if is_prime[i]]

def main():
  while True:
    n = int(input())
    if not n:
      break
        
    ans = 0
    for i in primes:
      if i > n // 2:
        break
      if is_prime[n - i]:
        ans += 1
  
    print(ans)

main()

Submission status: Accepted

Solution code:
# AOJ 0056 Goldbach's Conjecture
# Python3 2018.6.16 bal4u

MAX = 50000
HALF = 2761			# prime[2760]=24989, prime[2761]=25013

prime = [
  3,  5,  7, 11, 13, 17, 19, 23, 29, 
 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 
 73, 79, 83, 89, 97,101,103,107,109,113, 
127,131,137,139,149,151,157,163,167,173, 
179,181,191,193,197,199,211,223 ]

sqp = [				# sqp[i] = prime[i]**2
  9,25,49,121,169,289,361,529,841,961,
1369,1681,1849,2209,2809,3481,3721,4489,5041,
5329,6241,6889,7921,9409,10201,10609,11449,11881,12769,
16129,17161,18769,19321,22201,22801,24649,26569,27889,29929,
32041,32761,36481,37249,38809,39601,44521,49729 ]

tbl = [0]*(MAX+1)	# zero if prime 
ans = [0]*(MAX+1)
ans[4] = 1

for i in range(47):
	for j in range(sqp[i], MAX, prime[i]): tbl[j] = 1;

for i in range(225, MAX+1, 2):
	if tbl[i] == 0: prime.append(i)

for i in range(HALF):
	j = i
	while True:
		k = prime[i]+prime[j]
		if k > MAX: break
		ans[k] += 1
		j += 1

while True:
	n = int(input())
	if n == 0: break
	if (n & 1) == 1: print(1-tbl[n-2])
	else: print(ans[n])