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:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0056
"""
from math import sqrt, ceil, pow


# 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 solve(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


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

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

Submission status: Time Limit Exceeded

Solution code:
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):
    result = 0
    sub_primes = set(x for x in primes if x < num)
    for x in sub_primes:
        if (num-x) in sub_primes:
            # print('solve1: {} + {} = {}'.format(x, num-x, num))
            result += 1
            if (num-x)*2 == num:
                result += 1
    return result//2


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):
    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 = solve3(num, A.primes)
        print(result)

Submission status: Time Limit Exceeded

Solution code:
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):
    result = 0
    sub_primes = set(x for x in primes if x < num)
    for x in sub_primes:
        if (num-x) in sub_primes:
            # print('solve1: {} + {} = {}'.format(x, num-x, num))
            result += 1
            if (num-x)*2 == num:
                result += 1
    return result//2


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):
    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: Time Limit Exceeded

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):
    # 7.43[s]
    result = 0
    list_primes = [x for x in primes if x < num]
    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
#            if (num-x)*2 == 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: Time Limit Exceeded

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
    set_primes = set(x for x in primes if x < num)
    for x in 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: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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)
    tmp = values[:I]
    print(sum(n - t in tmp for t in tmp))

Submission status: Time Limit Exceeded

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

while True:
    n = int(input())
    if n == 0:
        break
    elif n%2 == 1:
        print(0)
        continue
    cnt = 0
    for i in range(n):
        if c[i] == 1 and c[n-i] == 1:
            cnt +=1
    print(cnt)

Submission status: Time Limit Exceeded

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

while True:
    n = int(input())
    if n == 0:
        break
    elif n%2 == 1:
        print(0)
        continue
    cnt = 0
    for i in range(n):
        if c[i] == 1 and c[n-i] == 1:
            cnt +=1
    print(cnt)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

cnt_pair = [0 for i in range(n)]
for i in range(n):
    cnt = 0
    if i%2 == 0:
        for j in range(n):
            if is_prime[j] and is_prime[n - j]:
                cnt += 1
        cnt_pair[i] = cnt

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

Submission status: Time Limit Exceeded

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

cnt_pair = [0 for i in range(n)]
for i in range(n):
    cnt = 0
    if i%2 == 0:
        for j in range(0, n//2):
            if is_prime[j] and is_prime[n - j]:
                cnt += 1
        cnt_pair[i] = cnt

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

Submission status: Time Limit Exceeded

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

cnt_pair = [0 for i in range(n)]
for i in range(n):
    if is_prime[i]:
        for j in range(i, n):
           if i + j >= n:
               break
           if is_prime[j]:
               cnt_pair[i + j] += 1

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

Submission status: Time Limit Exceeded

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

cnt_pair = [0 for i in range(n)]
for i in range(n//2):
    if is_prime[i]:
        for j in range(i, n - i):
           if is_prime[j]:
               cnt_pair[i + j] += 1

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

Submission status: Time Limit Exceeded

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

cnt_pair = [0 for i in range(n)]
for i in range(3, n//2, 2):
    if is_prime[i]:
        for j in range(i, n - i, 2):
           if is_prime[j]:
               cnt_pair[i + j] += 1

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

Submission status: Time Limit Exceeded

Solution code:
def get_input():
    while True:
        try:
            yield ''.join(input())
        except EOFError:
            break

MAX = 50000
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: Time Limit Exceeded

Solution code:
def get_input():
    while True:
        try:
            yield ''.join(input())
        except EOFError:
            break

MAX = 50000
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
    if N % 2 == 0:
        for i in range(1,N//2 + 1):
            if primes[i] and primes[N-i]:
                ans += 1
    else:
        if primes[2] and primes[N-2]:
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def get_input():
    while True:
        try:
            yield ''.join(input())
        except EOFError:
            break

MAX = 50001
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

primeList = []
for i in range(MAX):
    if primes[i]:
        primeList.append(i)
ans = [0 for i in range(MAX*2+1)]

for i in range(len(primeList)):
    for j in range(i, len(primeList)):
        k = primeList[i] + primeList[j]
        ans[k] += 1

while True:
    N = int(input())
    if N == 0:
        break
    print(ans[N])

Submission status: Time Limit Exceeded

Solution code:
from itertools import *
n=range(49994);a=list(n)
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 a,b in combinations_with_replacement(p[:x],2)if a+b==x))

Submission status: Time Limit Exceeded

Solution code:
from itertools import *
n=range(49994);a=list(n)
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)
 if x%2:print(sum(1 for c in p[1:x]if 2+c==x))
 elif x-4:print(sum(1 for a,b in combinations_with_replacement(p[1:x],2)if a+b==x))
 else:print(1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import *
n=range(49994);a=list(n)
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)
 if x%2:print(sum(1 for c in p[1:x]if 2+c==x))
 elif x-4:print(sum(1 for a in p[1:x]for b in p[1:x]if a+b==x))
 else:print(1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import *
n=range(49994);a=list(n)
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)
 if x%2:print(sum(1 for c in p[2:x]if 2+c==x))
 elif x-4:print(sum(1 for a,b in combinations_with_replacement(p[1:x],2)if a+b==x))
 else:print(1)

Submission status: Time Limit Exceeded

Solution code:
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 iter(input,'0'):x=int(x);y=x//2+1;print(sum(a[x-d]>0 for d in compress(n[:y],a[:y])))

Submission status: Time Limit Exceeded

Solution code:
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 iter(input,'0'):x=int(x);y=x//2+1;print(sum(a[x-d]>0 for d in a[:y]))

Submission status: Time Limit Exceeded

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:y=x//2+1;print(sum(1 for d in compress(n[:y],a[:y])if a[x-d]))

Submission status: Time Limit Exceeded

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
    
    primes_less_than_n = [i for i in primes if i <= n // 2]
    ans = 0
    for i in primes_less_than_n:
      if i > n // 2:
        break
      if is_prime[n - i]:
        ans += 1
  
    print(ans)

main()

Submission status: Time Limit Exceeded

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

MAX = 50001
HALF = 25000

prime = [True]*MAX
def sieve(max):
	for i in range(4, max, 2):
		prime[i] = False
	sqrt = int(max**0.5)
	print('Sqrt=',sqrt)
	for i in range(3, sqrt, 2):
		if prime[i] is True:
			for j in range(i*i, max, i):
				prime[j] = False
sieve(MAX)

ans = [0]*(MAX*2)
ans[4] = 1
for i in range(3, MAX, 2):
	if prime[i]: ans[i+2] = 1

for i in range(3, HALF, 2):
	if prime[i]:
		for j in range(i, MAX, 2):
			if prime[j]: ans[i+j] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
ub = 50000
primes = {2} | set(range(3, ub, 2))
du = primes.difference_update
for n in range(3, ub, 2):
    if n in primes:
        du(range(n*3, ub, n*2))

primes = list(primes)

while True:
    n = int(input())
    if n == 0:
        break
    l, r = 0, bisect_left(primes, n-2)
    ans = 0
    while l <= r:
        if primes[l]+primes[r] > n:
            r -= 1
        ans += (primes[l]+primes[r] == n)
        l += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python:
# -*- coding: utf-8 -*-

import sys

def make_prime_list(lim):
    lst = [True for i in xrange(lim + 1)]

    num = 2
    while num ** 2 <= lim:
        for i in xrange(num * 2, lim + 1, num):
            lst[i] = False
        num += 1
        while not lst[num]:
            num += 1
    return [i for i in xrange(2, lim + 1) if lst[i]]

def solve():
    prime_list = make_prime_list(50000)
    while True:
        n = input()
        if n > 0:
            count = 0
            index = 0
            rev_index = len(prime_list) - 1
            while index <= rev_index:
                while prime_list[index] + prime_list[rev_index] > n:
                    rev_index -= 1
                if prime_list[index] + prime_list[rev_index] == n:
                    count += 1
                index += 1
            print count
        else:
            sys.exit()

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python:
# -*- coding: utf-8 -*-

import sys

def make_prime_list(lim):
    lst = [True for i in xrange(lim + 1)]

    num = 2
    while num ** 2 <= lim:
        for i in xrange(num * 2, lim + 1, num):
            lst[i] = False
        num += 1
        while not lst[num]:
            num += 1
    return [i for i in xrange(2, lim + 1) if lst[i]]

def binary_search(n, prime_list):
    rLim = len(prime_list) - 1
    lLim = 0
    while lLim < rLim:
        middle = (rLim + lLim) / 2
        if prime_list[middle] == n:
            return middle
        elif prime_list[middle] < n:
            lLim = middle + 1
        else:
            rLim = middle - 1
    while prime_list[rLim] < n and rLim < len(prime_list) - 1:
        rLim += 1
    return rLim    

def solve():
    prime_list = make_prime_list(50000)
    while True:
        n = input()
        if n > 0:
            count = 0
            index = 0
            rev_index = binary_search(n, prime_list)
            while index <= rev_index:
                while prime_list[index] + prime_list[rev_index] > n:
                    rev_index -= 1
                if prime_list[index] + prime_list[rev_index] == n:
                    count += 1
                index += 1
            print count
        else:
            sys.exit()

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
n=5*10**4
p=[True]*n
p[0],p[1]=False,False
for i in xrange(2,int(n**0.5)+1):
    if p[i]==True:
        for j in xrange(i**2,n,i):
            p[j]=False
while True:
    n=input()
    if n==0:break
    c=0
    for i in xrange(n/2+1):
        if p[i] and p[n-i]:c+=1
    print c

Submission status: Time Limit Exceeded

Solution code:
N=50000+1
p=[True]*N
p[0],p[1]=False,False
for i in xrange(2,int(N**0.5)+1):
    if p[i]==True:
        for j in xrange(i**2,N,i):
            p[j]=False
while True:
    n=input()
    if n==0:break
    c=0
    for i in xrange(n/2+1):
        if p[i] and p[n-i]:c+=1
    print c

Submission status: Time Limit Exceeded

Solution code:

import sys


def solv(n):
    r = 0
    m = n / 2
    ps = filter(lambda x: x <= m, primes)
    for p in ps:
        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
    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)