백준 6588 골드바흐의 추측

import sys
ch = [0] * 1000001
for i in range(2, 1000001):
    if ch[i] == 0:
        for j in range(i * 2, 1000001, i):
            ch[j] = 1

while True:
    a = int(sys.stdin.readline())
    if a == 0:
        break
    
    for i in range(3, a // 2 + 1):
        if ch[i] == 0 and ch[a - i] == 0:
            print(f"{a} = {i} + {a - i}")
            break
    else:
        print("Goldbach's conjecture is wrong.")

에라토스테네스의 체를 이용하여 소수인 숫자를 0으로 표시하였다.

pypy3로 풀어야 시간초과가 나지 않는다.

import sys
ch = [0] * 1000001
for i in range(2, 1001):
    if ch[i] == 0:
        for j in range(i * 2, 1000001, i):
            ch[j] = 1

while True:
    a = int(sys.stdin.readline())
    if a == 0:
        break
    
    for i in range(3, a // 2 + 1):
        if ch[i] == 0 and ch[a - i] == 0:
            print(f"{a} = {i} + {a - i}")
            break
    else:
        print("Goldbach's conjecture is wrong.")

소수를 구할 때 반복을 조금이라도 줄이면 시간이 조금 빨라진다