[백준] 6588: 골드바흐의 추측 (Python)

문제📖

풀이🙏

• 에라토스테네스의 체를 이용하여 전체 수 만큼 True값을 가진 리스트를 생성한다.
• 2부터 시작하여 그 배수에 해당하는 값들을 False로 바꾸어 소수를 판별한다.
• array가 n, n-i가 모두 True인 경우 즉, 둘다 소수인 경우 출력한다.

코드💻

import sys
input = sys.stdin.readline

# 에라토스테네스의 체
# 전체 수 만큼 True 리스트 생성
# 2부터 1씩 더해주면서 그 배수에 해당하는 값들을 False로 바꾼다.
array = [True for i in range(1000001)]

for i in range(2, 1001):
    if array[i]:
        for k in range(i + i, 1000001, i):
            array[k] = False

while True:
    n = int(input())
    if n == 0: break
    
    for i in range(3, len(array)):
        if array[i] and array[n-i]:
            print(n, "=", i, "+", n-i)
            break