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 p1 and p2 such that n = p1 + p2.

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 (p1, p2) and (p2, p1) 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 215. 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



Sample input:
6
10
12
0


Sample output:
1
2
1

Submission status: Wrong Answer

Solution code:
# AOJ 1200: Goldbach's Conjecture
# Python3 2018.7.19 bal4u

MAX = 32770    # > 2^15
SQRT = 181     # sqrt(MAX)

prime = [True]*MAX
def sieve():
	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)

Submission status: Wrong Answer

Solution code:
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**14)
for line in sys.stdin:
    n = int(line)
    if n == 0:
        break
    c = goldbach(p, n)
    print(c)

Submission status: Wrong Answer

Solution code:
import math
primes=[2]
top=2
nlist=[2*x-1 for x in range(2,2**12)]
while top<math.sqrt(2**13):
    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

Submission status: Wrong Answer

Solution code:
import math
primes=[2]
top=2
nlist=[2*x-1 for x in range(2,2**13)]
while top<math.sqrt(2**14):
    top=nlist[0]
    primes.append(top)
    newnlist=[]
    for i in nlist:
        if i%top!=0:
            newnlist.append(i)
    nlist=newnlist
primes=primes+nlist
print primes
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:
                print (i,n-i)
                sum=sum+1
        print sum

Submission status: Wrong Answer

Solution code:
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
print primes
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:
                print (i,n-i)
                sum=sum+1
        print sum

Submission status: Wrong Answer

Solution code:
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:]
print(p)
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)

Submission status: Wrong Answer

Solution code:
import bisect
primes = [0, 0] + [1]*32767
for i in range(2, 181):
    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]))

Submission status: Wrong Answer

Solution code:
print(3)

Submission status: Accepted

Solution code:
# AOJ 1200: Goldbach's Conjecture
# Python3 2018.7.19 bal4u

MAX = 32770    # > 2^15
SQRT = 182     # sqrt(MAX)+1

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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
# coding: utf-8
# Here your code !
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]

# primes = []
# maxn = 0

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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]

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
#1200
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# coding: utf-8
# 80
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
    #print(a)
    s=primes(a)
    
    #print(s)
    c=0
    for r in itertools.combinations(s,2):
        if r[0]+r[1]==a:
            c += 1
            #print(r)
    if a/2 in s:
        c += 1
    print(c)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

#print(s)

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)

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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):
# Listからnumに最も近い値を返す

    Ind = list(map(Sub, List))
    ind = min(Ind)
    # list要素とnumの差分を計算し最小値のインデックスを取得
    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)

Submission status: Accepted

Solution code:
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)

Submission status: Runtime Error

Solution code:
MAX=2**15
a = range(MAX)
a[1] = 0
for p in a:
    if not p:
        continue
    elif p > 100:
        break
    else:
        for multi in xrange(p+p, MAX, p):
            a[multi] = 0

ans = []
while True:
    n=input()
    sig=0
    if n==0:
        break
    for i in a:
        if i>(n/2):
            break
        for j in reversed(a):
            if (i+j) == n:
                sig += 1
            if j == i:
                break
    ans.append(sig)
for i in ans:
    print i

Submission status: Runtime Error

Solution code:
MAX=33000
a = range(MAX)
a[1] = 0
for p in a:
    if not p:
        continue
    elif p > 100:
        break
    else:
        for multi in xrange(p+p, MAX, p):
            a[multi] = 0

ans = []
while True:
    n=input()
    sig=0
    if n==0:
        break
    for i in a:
        if i>(n/2):
            break
        for j in reversed(a):
            if (i+j) == n:
                sig += 1
            if j == i:
                break
    ans.append(sig)
for i in ans:
    print i