[백준6588번] 골드바흐의 추측 / Python3

문제

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."을 출력한다.

예제 입력 1

8
20
42
0

예제 출력 1

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

나의 풀이

이 문제는 n이 1,000,000까지로 제한이 되어있어 입력을 받기 전에 1,000,000까지의 에라토스테네스의 채를 만들어 놓으면 시간을 많이 절약할 수 있다. 처음에는 에라토스테네스의 채를 만들면서 홀수인 소수만을 따로 골라내어 for문을 돌려보았지만 시간초과가 나서 현재의 풀이대로 풀었더니 성공을 했다.

에라토스테네스의 채를 만들었다면 i를 3부터 홀수만 반복을 한다. (즉, 3부터 2씩 증가를 시킨다.) 그리고 n-i가 소수인지 확인한다. 만약 i와 n-i 모두 소수라면 break로 반복문을 빠져나와 출력을 한다. 왜 n-i가 홀수인지를 확인 안하는가하면 짝수에서 홀수를 빼면 무조건 홀수가 나오기때문이다. 에라토스테네스를 안다면 쉽게 풀 수 있는 문제였다.

코드

# 6588번 골드바흐의 추측

# 에라토스테네스의 채
eratos = [True for _ in range(1000001)]
for i in range(2,1000001):
    if eratos[i]:
        x = i*i
        while x < 1000001:
            eratos[x] = False
            x += i

# main
while True:
    n = int(input())

    if n == 0:
        break

    isPos = False
    for i in range(3,n,2):      # 3부터 2씩 증가시키면 홀수만 확인
        if eratos[i] and eratos[n-i]:       # 짝수에서 홀수를 빼면 홀수
            a = i
            b = n - i
            isPos = True
            break

    if isPos:
        print(str(n) + " = " + str(a) + " + " + str(b))
    else:
        print("Goldbach's conjecture is wrong.")