[알고리즘 문제 풀이][파이썬] 백준 6588번: 골드바흐의 추측

백준 6588 문제 링크: https://www.acmicpc.net/problem/6588

📑 문제 설명

골드바흐의 추측: 4 이상의 짝수는 두 홀수인 소수의 합으로 나타낼 수 있음.

6보다 크거나 같고, 1000000보다 작거나 같은 짝수가 주어질 때, 주어진 수에 대해 홀수이자 소수로 이루어진 두 수를 구하는 프로그램 작성.

입력: 6보다 크고 1000000보다 작은 짝수(0을 입력시 프로그램 종료)
출력: "n = a + b" 로 출력. 만약 나타낼 숫자가 없다면 "Goldbach's conjecture is wrong." 출력

💡 문제 해결 방법

시간 초과를 유의해야 하는 문제.

key point
1. 소수를 구할 때는 에라토스테네의 체 를 사용한다.
2. 0 입력되기 전까지 소수를 구해야 하기 때문에 반복문 돌기 전에 한 번만 1000000이하의 소수를 구해놓는다.
(2번 때문에 시간초과 걸리는 줄도 모르고...😂)

💻 코드

import sys


if __name__ == '__main__':
    t = -1

    tf_list = [True for i in range(1000001)]
    tf_list[0] = False
    tf_list[1] = False
    for i in range(2, 1001):
        if (tf_list[i] == True):
            for k in range(i + i, 1000001, i):
                tf_list[k] = False


    while(1):
        t = int(sys.stdin.readline())

        if t == 0:
            break

        check = -1
        for i in range(3, t, 2):
            if (tf_list[i] and tf_list[t - i]):
                print(t, "=", i, "+", t - i)
                check = 1
                break
        if (check == -1):
            print("Goldbach's conjecture is wrong.")

💟 추가적으로 알게 된 점

• 시간 초과가 나는 이유를... 파악하자...