Problem:
Problem A: Goldbach's Conjecture  Goldbach's Conjecture: For any even number n greater than or equal to 4, there exists at least one pair of prime numbers p 1 and p 2 such that n = p 1 + p 2 . This conjecture has not been proved nor refused yet. No one is sure whether this conjecture actually holds. However, one can find such a pair of prime numbers, if any, for a given even number. The problem here is to write a program that reports the number of all the pairs of prime numbers satisfying the condition in the conjecture for a given even number. A sequence of even numbers is given as input. Corresponding to each number, the program should output the number of pairs mentioned above. Notice that we are intereseted in the number of essentially different pairs and therefore you should not count ( p 1 , p 2 ) and ( p 2 , p 1 ) separately as two different pairs. Input An integer is given in each input line. You may assume that each integer is even, and is greater than or equal to 4 and less than 2 15 . The end of the input is indicated by a number 0. Output Each output line should contain an integer number. No other characters should appear in the output. Sample Input 6
10
12
0 Output for the Sample Input 1
2
1

Solution (Python):



MAX = 32770    
SQRT = 182     

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

sieve()
while True:
    n = int(input())
    if n == 0: break
    if n == 4: ans = 1
    else:
        ans = 0
        for i in range(3, 1+(n>>1), 2):
            if prime[i] and prime[n-i]: ans += 1
    print(ans)

Solution (Python):
import sys
import math

def primes(n):
    sieve = [1] * (n + 1)
    rt = int(math.sqrt(n))
    sieve[0] = sieve[1] = 0
    for p in range(2, rt + 1):
        if sieve[p] == 0:
            continue
        k = p * 2
        while k <= n:
            sieve[k] = 0
            k += p
    r = []
    for p in range(2, n + 1):
        if sieve[p] == 1:
            r.append(p)
    return r

def goldbach(prime, n):
    c = 0
    for p in prime:
        if p <= n - p and n - p in prime:
            c += 1
    return c

p = primes(2**15)
for line in sys.stdin:
    n = int(line)
    if n == 0:
        break
    c = goldbach(p, n)
    print(c)

Solution (Python):
import math
primes=[2]
top=2
nlist=[2*x-1 for x in range(2,2**14)]
while top<math.sqrt(2**15):
    top=nlist[0]
    primes.append(top)
    newnlist=[]
    for i in nlist:
        if i%top!=0:
            newnlist.append(i)
    nlist=newnlist
primes=primes+nlist
while(1):
    n=int(raw_input())
    if n==0:
        break
    else:
        sum=0
        for i in range(2,n/2+1):
            if i in primes and n-i in primes:
                sum=sum+1
        print sum

Solution (Python):


def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False

def sieve(n):
    s = [True] * n
    for x in range(2, int(n**0.5) + 1):
        if s[x]: 
            mark(s, x)
    return [i for i in range(0,n) if s[i] and i > 1]




while True:
    n = int(input())
    if n == 0:
        break
    
    
        
    primes = sieve(n)
    
    
    count = 0
    for prime in primes:
        if prime > (n // 2):
            print(count)
            break
        else:
            if (n - prime) in primes:
                count += 1

Solution (Python):
N=32768
p=[i for i in range(N)]
for i in range(2,int(N**0.5)+1):
    if p[i]:
        for j in range(i*i,N,i):p[j]=0
p=sorted(set(p))[2:]
while 1:
    n=int(input())
    if n==0:break
    c=0
    if n&1:c=int(n-2 in p)
    else:
        for x in p:
            if x>n//2:break
            if n-x in p:c+=1
    print(c)

Solution (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_value = [i for i in range(2, 32769) if primes[i]]
while True:
    n = int(input())
    if n == 0:
        break
    x = bisect.bisect_left(prime_value, n//2)
    y = bisect.bisect_left(prime_value, n)
    values = prime_value[x:y]
    print(sum(1 for v in values if primes[n-v]))

Solution (Python):
import math

def primes(x):
    if x<2: return []
    primes = [i for i in range(x)]
    primes[1] = 0

    for prime in primes[:int(math.sqrt(x))+1]:
        if prime > 0:
            for not_prime in range( 2*prime, x, prime ): primes[not_prime] = 0

    return [prime for prime in primes if prime != 0]



while True:
    n = input()

    if n <= 0: break

    primelist = primes(n)

    print (len([prime for prime in primelist if (n-prime in primelist)])+1)/2

Solution (Python):
from itertools import takewhile
primes = [0, 0] + [1] * (2**15)
for i in range(2, 182):
    if primes[i]:
        for j in range(i*i, 2**15 + 2, i):
            primes[j] = 0

while True:
    n = int(input())
    if n == 0:
        break
    prime_values = [i for i in range(len(primes[:n])) if primes[i]]
    print(sum(n-p1 in prime_values for p1 in takewhile(lambda x: x < n//2+1, prime_values)))

Solution (Python):
from itertools import takewhile
primes = [0, 0] + [1] * (2**15)
for i in range(2, 182):
    if primes[i]:
        for j in range(i*i, 2**15 + 2, i):
            primes[j] = 0

while True:
    n = int(input())
    if n == 0:
        break
    prime_values = [i for i in range(len(primes[:n])) if primes[i]]
    print(sum(n-p1 in prime_values for p1 in takewhile(lambda x: x < n//2+1, prime_values)))

Solution (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]))

Solution (Python):
M = 2**15+1
isPrime = [True]*M
isPrime[0],isPrime[1]=False,False
for i in xrange(M):
    if isPrime[i]:
        for j in xrange(i*i,M,i):
            isPrime[j] = False
while 1:
    n = input()
    if n==0: break
    ans = 0
    for i in xrange(2,n/2+1):
        if isPrime[i] and isPrime[n-i]: ans+=1
    print ans

Solution (Python):
M = 2**15+1
isPrime = [True]*M
isPrime[0],isPrime[1]=False,False
p = []; ans = [0]*M;
for i in xrange(M):
    if isPrime[i]:
        for j in xrange(i*i,M,i):
            isPrime[j] = False
        p.append(i)
for i in xrange(len(p)):
    for j in xrange(i,len(p)):
        if p[i]+p[j]>=M: break
        ans[p[i]+p[j]]+=1
while 1:
    n = input()
    if n==0: break
    print ans[n]

Solution (Python):
r = 2**15+1
sqrt = int(r**0.5)
p = [1]*(r+1)
p[:2] = [0,0]
for i in range(2,sqrt+1):
	if p[i]:
		p[2*i::i] = [0 for x in range(2*i,r+1,i)]
while 1:
	n = input()
	if n == 0: break
	count = 0
	for i in range(2,n/2+1):
		if p[i] and p[n-i]:
			count += 1
	print count

Solution (Python):
N=32768
p=[ i for i in range(N)]
for i in range(2, int(N**0.5)+1):
    if p[i]:
        for j in range(i*i,N,i):
            p[j]=0

p=sorted(set(p))[2:]
while True:
    n = int(input())
    if n==0:
        break
    c=0
    if n&1:c=int(n-2 in p)
    else:
        for x in p:
            if x>n//2:
                break
            if n-x in p:
                c += 1
    print(c)

Solution (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]))

Solution (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]))

Solution (Python):
def f(x):
    if x == 2:
        return 1
    if x < 2 or x % 2 == 0:
        return 0
    i = 3
    while i <= x ** (1/2):
        if x % i == 0:
            return 0
        i += 2
    return 1
while True:
    n = int(input())
    if n == 0:
        break
    else:
        a = 0
        for i in range(1, n // 2 + 1):
            m = n - i
            if f(m) == 1 and f(i) == 1:
                a += 1
        print(a)

Solution (Python):



MAX = 2 ** 15
s = [1] * MAX
s[0] = 0
s[1] = 0

start = 2
while True:
   pmb = 0
   for i in range(start, MAX):
      if s[i] == 1:
         pmb = i
         break
   if pmb == 0:
      break
   
   for i in range(pmb ** 2, MAX, pmb):
      s[i] = 0

   start += 1

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

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

   print(c)

Solution (Python):
def f(x):
    if x == 2:
        return 1
    if x < 2 or x % 2 == 0:
        return 0
    i = 3
    while i <= x ** (1/2):
        if x % i == 0:
            return 0
        i += 2
    return 1
    
while True:
    n = int(input())
    if n == 0:
        break
    else:
        a = 0
        for i in range(2, n // 2 + 1):
            m = n - i
            if f(m) == 1 and f(i) == 1:
                a += 1
        print(a)

Solution (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]))

Solution (Python):
def f(x):
    if x==2:
        return 1
    if x<2 or x%2==0:
        return 0
    i=3
    while i<=x**(1/2):
        if x%i==0:
            return 0
        i+=2
    return 1

while True:
    n=int(input())
    if n==0:
        break
    else:
        s=0
        for i in range(2,n//2+1):
            m=n-i
            if f(m)==1 and f(i)==1:
                s+=1
        print(s)

Solution (Python):
import math as m

def prime(n):
    if n <= 1:
        return False
    for i in range(2,int(m.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def Goldbach(n):
  x = []
  c = 0
  for i in range(n+1):
    if prime(i):
      x.append(i)
  for j in x:
    for k in x:
      if j > k:
        pass
      elif j + k == n:
            c += 1
      else:
        pass
  print(c)

while 1:
  n = int(input())
  if n == 0:
    break
  Goldbach(n)

Solution (Python):
import math
def Sosu(N) :
    for i in range(2, int(math.sqrt(N))+1) :
        if N % i == 0 :
            return False
    return True
    
def main(a) :
    count = 0
    for i in range(2, a) :
        if Sosu(i) :
            other = a - i
            if other >= i and Sosu(other) :
                count += 1
    return count

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

Solution (Python):

def primes(x):
    is_prime = [True] * (x + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(x**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, x + 1, i):
            is_prime[j] = False
    return [i for i in range(x + 1) if is_prime[i]]

while True:
    c = 0
    d = 0
    n = int(input())
    if n == 0:
        break
    z = primes(n)
    for i in z:
        for j in z:
            if (i+j) == n:
                c += 1
                if i != j:
                    d += 1
    print(c-int(d/2))

Solution (Python):
import math
def kosu(n):
    l=[]
    sosu = [True] * (n + 1)
    sosu[0]= False
    sosu[1]= False
    for i in range(2,math.floor(math.sqrt(n))+1):
        if not sosu[i]:
            continue
        for j in range(i*2,n+1,i):
            sosu[j] = False
    for i in range(len(sosu)):
        if sosu[i]:
            l.append(i)
    return(l)
    
while True:
    n = int(input())
    if n == 0:
        break
    ln = kosu(n)
    ans = 0
    for i in ln:
        for j in ln:
            x = i + j
            if x == n:
                ans += 1
                ln.remove(j)
    print(ans)

Solution (Python):
def sosu(n):
    if n<=1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
    return True
def gold(n):
    a=[]
    b=0
    for i in range(n+1):
        if sosu(i):
            a.append(i)
    for j in a:
        for k in a:
            if j>k:
                pass
            elif j+k==n:
                b+=1
            else:
                pass
    print(b)
while True:
    n=int(input())
    if n==0:
        break
    gold(n)

Solution (Python):


import itertools

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n+ 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
    

while True:
    a=int(input())
    if a==0:
        break
    
    s=primes(a)
    
    
    c=0
    for r in itertools.combinations(s,2):
        if r[0]+r[1]==a:
            c += 1
            
    if a/2 in s:
        c += 1
    print(c)

Solution (Python):
p = [True for i in range(1000001)]
p[0] = False
p[1] = False
for i in range(2,500000):
  for j in range(2, 1000000//i + 1):
    p[i * j] = False

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

Solution (Python):
def f(x):
    if x==2:
        return 1
    if x<2 or x%2==0:
        return 0
    i=3
    while i<=x**(1/2):
        if x%i==0:
            return 0
        i+=2
    return 1
while True:
    n=int(input())
    if n==0:
        break
    else:
        p=0
        for i in range(2,n//2+1):
            m=n-i
            if f(m)==1 and f(i)==1:
                p+=1
        print(p)

Solution (Python):
def f(x):
    if x==2:
        return 1
    if x<2 or x%2==0:
        return 0
    i=3
    while i<=x**(1/2):
        if x%i==0:
            return 0
        i+=2
    return 1

while True:
    n=int(input())
    if n==0:
        break
    else:
        s=0
        for i in range(2,n//2+1):
            m=n-i
            if f(m)==1 and f(i)==1:
                s+=1
        print(s)

Solution (Python):
import math
def Sosu(N) :
    for i in range(2, int(math.sqrt(N))+1) :
        if N % i == 0 :
            return False
    return True
    
def main(a) :
    count = 0
    for i in range(2, a) :
        if Sosu(i) :
            other = a - i
            if other >= i and Sosu(other) :
                count += 1
    return count

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

Solution (Python):
MAX = 2 ** 15
s = [1] * MAX
s[0] = 0
s[1] = 0

start = 2
while True:
   pmb = 0
   for i in range(start, MAX):
      if s[i] == 1:
         pmb = i
         break
   if pmb == 0:
      break
   
   
   for i in range(pmb ** 2, MAX, pmb):
      s[i] = 0

   start += 1



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

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

   print(c)

Solution (Python):
import math

def prime(n):
    nlist = list(range(2,n+1))
    sosu = []
    
    while True:
        if nlist[0]>math.sqrt(n):
            sosu.extend(nlist)
            break
        else:
            nlist0 = nlist[0]
            sosu.append(nlist0)
            nlist.pop(0)
            nlist = [num for num in nlist if num%nlist0 != 0]
    
    return sosu

while True:
    n = int(input())
    
    if n==0:
        break
    
    nsosu = prime(n)       
    
    count = 0
    for i in range(len(nsosu)):
        p = n-nsosu[i]
        if p in nsosu:
            count += 1
    
    Count = int((count+1)/2)
    print(Count)
    
    continue

Solution (Python):
import math as m

def prime(n):
    if n <= 1:
        return False
    for i in range(2,int(m.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def Goldbach(n):
  x = []
  c = 0
  for i in range(n+1):
    if prime(i):
      x.append(i)
  for j in x:
    for k in x:
      if j > k:
        pass
      elif j + k == n:
            c += 1
      else:
        pass
  print(c)

while 1:
  n = int(input())
  if n == 0:
    break
  Goldbach(n)

Solution (Python):
p=[1 for i in range(1000001)]
p[0]=0
p[1]=0
for i in range(2,500000):
    for j in range(2,1000000//i+1):
        p[i*j]=0

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

Solution (Python):
import math

P = []

Max = 1000000

def Era(P, Max) :
    D = list(range(2, Max))
    limit = math.sqrt(Max)
    while True :
        p = D[0]
        
        if limit <= p :
            P += D
            return P
        
        P.append(p)
        D = [d for d in D if d % p != 0]
        
def Sub(x) :
    return abs(x - n)

def Sub2(x) :
    return abs(x - n // 2)

def Near(List, num):


    Ind = list(map(Sub, List))
    ind = min(Ind)
    
    return Ind.index(ind)

def Near2(List, num):

    Ind = list(map(Sub2, List))
    ind = min(Ind)
    return Ind.index(ind)

Era(P, Max)

while True :
    n = int(input())
    
    if n == 0 :
        break
    else :
        l = Near2(P, n // 2) + 1
        N = Near(P, n) + 1
        cnt = 0
        s = 0
        I = []
        
        for i in range(N + 1, l - 2, -1) :
            for j in range(s, l + 1) :
                if n == P[i] + P[j] :
                    if P[j] not in I :
                        cnt += 1
                        s = j
                        I.append(P[i])
                        
                elif n < P[i] + P[j] :
                    break
                    
        print(cnt)

Solution (Python):
p = [True for i in range(1000001)]
p[0] = False
p[1] = False
for i in range(2,500000):
  for j in range(2, 1000000//i + 1):
    p[i * j] = False

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

Solution (Python):
import math

Q_MAX = 2 << 15


def primes(n):
    p = [True] * (n + 1)
    p[0] = p[1] = False
    for i in range(2, int(math.sqrt(n + 1))):
        if p[i]:
            for j in range(i * 2, n + 1, i):
                p[j] = False
    return p


P = [i for i, x in enumerate(primes(Q_MAX)) if x]

while True:
    q = int(input())
    if q == 0: break
    count = 0
    for p in P:
        if p > q / 2:
            break
        if q - p in P:
            count += 1
    print(count)