[수학] 백준 6588번 골드바흐의 추측 with 파이썬

https://www.acmicpc.net/problem/6588
시간초과가 아주 밥먹듯이 난 문제였다.
이거해도 시간초과 저거해도 시간초과~

import sys
input = sys.stdin.readline

prime = [True for _ in range(1000001)]

for i in range(2,1001):
    if prime[i]:
        for j in range(2*i, 1000001, i) : 
            if prime[j] :
                prime[j] = False            

while(True):                     
    n = int(input())

    if n==0 : break
    for i in range(3,1000001,2):
        if prime[i] and prime[n-i]:
            print("%d = %d + %d"%(n , i , n-i))
            break

첫번째로 소수를 구하는 부분을 내가 원래 쓰던 코드가 아닌 조건문에 걸릴 때만 돌아갈 수 있게 조금 덜 돌아가는 코드로 바꾸었다.
두번째로는 어짜피 짝수는(2제외) 소수가 아니므로 1씩 올리지 않고 2씩 올려주었더니 시간초과가 해결되었다.
레퍼런스를 많이 참고한 문제였다.