백준 알고리즘 6588번 골드바흐의 추측(python)

에라토스테네스의 체를 사용해야 하는 소수 문제이다. 9020번 골드바흐의 추측 문제와 비슷한 문제인데 

시간 초과 관련해서 더 훨씬 힘든 것 같다.

핵심은 1000000 까지의 소수를 미리 다 찾아놓고 while문을 돌리는 것이다. 안 그러면 시간 초과가 나온다. 

import sys

li = [1]*(1000001)
for i in range(2, int(1000001**0.5) + 1):
    if li[i] == 1:
        for j in range(i+i, 1000001, i):
            li[j] = 0

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