[백준/6588/파이썬] 골드바흐의 추측

---

소스코드

import sys

dp = [1] * (1000000 + 1)

dp[0] = 0

dp[1] = 0

for i in range(2, 1001):  #dp에 소수를 넣는 과정 (에라토스테네스의 체)

    if dp[i]:

        for j in range(i * i, 1000001, i):

            dp[j] = 0

def goldba(n):

    for i in range(2, n):

        if dp[i] and dp[n - i]:

            print(f'{n} = {i} + {n - i}')

            return 0 

    return 1    # 골드바흐 가설이 틀린걸 증명 해버림

while (1):

    try:

        n = int(sys.stdin.readline())

        if n == 0: 

            break

        if goldba(n): 

            print("Goldbach's conjecture is wrong.")

    except EOFError:

        break

---

알고리즘

에라토스테네스의 체를 사용하여 dp에 소수를 0과 1로 구분하여 입력해주고 

n을 넣었을때 소수끼리 더한 수(dp가 둘다 참)이면 출력 후 함수 종료를 하면 된다.

시간초과가 여러번 났던 문제라서 다른 풀이를 보고 소수를 넣는 방법에 대해 시간을 줄일 수 있었다.

       if n == 0: 

            break

이걸 안해줘서 골드바흐 가설이 틀린걸 증명할뻔했따...