백준 6588 파이썬 python : 골드바흐의 추측 @@황소처럼 우직하게@@ 에레토스테네스의 체 + 최적화

에레토스테네스의 체 구현해도 시간초과나서

최적화하는데 꽤 걸렷네요

import sys
input = sys.stdin.readline

num_list = []

while True:
    n = int(input().strip())
    if n == 0:
        break
    num_list.append(n)


max_num = max(num_list)

sosu = [1 for i in range(max_num + 1)]
sosu[1] = 0
only_sosu = []

i = 2
while i <= max_num:
    if sosu[i] == 1:
        only_sosu.append(i)
        for j in range(i + i, max_num + 1, i):
            sosu[j] = 0
    i += 1

for x in num_list:
    for n1 in only_sosu:
        if sosu[x - n1] == 1:
            print("%d = %d + %d" %(x, n1, x - n1))
            break

위에는 평범하게 에레토스테네스의 체로 소수 구해주고

소수들만 담은 리스트 따로 뽑아낸 다음에

마지막에 두 소수 찾아낼 때,

N - 소수가 소수 인지 판단해주면 돼요 (최적화 부분)

풀면서 아.. 멍청이