6588번 파이썬

def filtering(n):
    lists=[True] * n
    for i in range(2,int(n**0.5)+1):
        if lists[i]:
            for j in range(i*2,n,i):
                lists[j]=False
    
    return [i for i in range(2,n) if lists[i]]

# 처음엔 에라토스테네스의 체를 이용해서 n보다 작은 소수의 배열을 반환하는 함수를 만들려 했지만

매번 새로 만들어서 그런지 시간 초과가 계속 뜸 따라서 n의 max인 1000000보다 작은 소수 배열을 미리 만들어서 사용

 

 

import sys
input = sys.stdin.readline

num = 1000001
lists=[True] * num
for i in range(2,int(num**0.5)+1):
    if lists[i]:
        for j in range(i*2,num,i):
            lists[j]=False

while 1:
    n=int(input())
    if n==0:
        break
    bool = False
    for i in range(2,n+1):
        if lists[i] and lists[n-i]: 
            bool = True
            print("%d = %d + %d" % (n,i,n-i))
            break # i보다 크게 되면 차잇값이 그만큼 작아지므로 종료!
       
    if not bool:
        print("Goldbach's conjecture is wrong")​