[알고리즘][백준] 6588번 골드바흐의 추측 - 파이썬(python) 풀이

https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

---

에라토스테네스의 체를 이용해서 소수를 빠르게 찾아 진행

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

import sys

# 소수 판정

sosu = [True] * 1000001

for i in range(2, int(len(sosu)**0.5)+1):

    if sosu[i]:     # sosu[i] == True

        for j in range(2*i, 1000001, i):    # i의 배수 != 소수

            sosu[j] = False

while True:

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

    if input == 0:

        break

    for i in range(input-3, 2, -2):     # 두 홀수 소수(3~input-3)의 합

        if sosu[i] and sosu[input-i]:       # sosu[i] & sosu[input-i] == True

            print(f"{input} = {input-i} + {i}")

            break

    else:

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