백준 6588번. 골드바흐의 추측 (Python / 파이썬)

문제

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.
 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.
예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.
이 추측은 아직도 해결되지 않은 문제이다.
백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.
각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)
입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

---

문제 풀이

골드바흐의 추측은 4보다 큰 모든 짝수는 두 홀수 소수의 합으로

나타낼 수 있다는 것입니다.

따라서 만약 어떤 짝수 정수 n이 주어졌을 때

이를 검증하는 문제입니다.

 

골드바흐의 추측을 검증하기 위해서는 어떤 수가 소수인지 아닌지

판별하는 과정이 필요합니다. 

따라서 True로 초기화된 check list를 만들어 

소수 인지 아닌지 각 수를 판별해주었습니다.

어떤 수의 배수들을 모두 False로 바꿔주면 소수를 구할 수 있습니다.

 

만약 어떤 수 i와 n-i 가 모두 True라면 둘 다 소수라는 것이므로

결과를 출력해줍니다.

차이가 가장 큰 결과를 출력하라 했으므로 제일 작은 수부터 확인하고

break로 종료시켜줍니다. 

---

My Code

import sys
input = sys.stdin.readline

check = [True] * 1000001 # 소수인지 판별할 list
check[1] = False # 1은 소수가 아니므로 False
for i in range(2, 1000001):
    for j in range(i + i, 1000001, i): # 배수들은 소수가 아니므로
        check[j] = False               # False로 바꿔줌

while True:
    n = int(input()) # 짝수 정수 n

    if n == 0: # 0이 입력되면 종료
        break

    for i in range(2, n):
        if check[i] and check[n - i]: # 합이 n이 되는 수들이 소수라면
            print(n, '=', i, '+', n - i) # 식 출력
            break # 종료