[🥈1 / 백준 6588 / 파이썬] 골드바흐의 추측

 

6588번: 골드바흐의 추측

 

문제

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

 

예제 입력  8 20 42 0

예제 출력  8 = 3 + 5 20 = 3 + 17 42 = 5 + 37

 

풀이

 

주어진 짝수를 두 소수의 합으로 나타내되, b-a 가 가장 큰 것을 출력하는 문제이다.

 

먼저 에라토스테네스의 체로 소수 최대 입력값인 1,000,000 까지의 소수 판정 리스트를 구한다.

그리고 필자는 연산을 절약하기 위해 소수 리스트를 따로 구해줬는데, 딱히 구하지 않아도 AC를 받는 데에 상관은 없다.

에라토스테네스의 체에 관한 내용은 아래 포스트에 기재돼있다.

 

[백준 1929] 기본 수학 2 - 소수 구하기 (에라토스테네스의 체)

 

이제 입력받은 수에 대해 소수 리스트의 처음부터 빼가며, 뺀 나머지도 소수라면 그것을 출력하면 된다.

만약 뺄 소수가 입력받은 수보다 크다면 골드바흐의 추측이 틀렸으므로 "Goldbach's conjecture is wrong."를 출력하자.

하지만 위 예외사항을 빼고 제출해도 통과하는 것을 보니 문제의 최대 입력값에 대해서는 일단 그의 추측이 맞는 것 같다.

 

import sys
input = sys.stdin.readline
print = sys.stdout.write
MAX = 1000001

def solve():
    # 에라토스테네스의 체
    sieve = [False]*2 + [True]*(MAX-2)
    for i in range(3,int(MAX**0.5),2):
        if sieve[i]:
            sieve[i*2::i] = [False]*((MAX-i-1)//i)

    # 소수 리스트 구하기
    prime = []
    for i in range(3,MAX,2):
        if sieve[i]:
            prime.append(i)

    # 추측 검증
    while True:
        n = int(input())
        if not n:
            break

        for i in prime:
            if sieve[n-i]:
                print("%d = %d + %d\n" %(n,i,n-i))
                break
solve()

 

파이썬에서 3위를 했다! 뿌듯