[백준] 골드바흐의 추측

최동혁·2022년 12월 6일

baekjoon python 알고리즘

백준

목록 보기

49/68

골드바흐의 추측

문제

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

예제 출력 1

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

문제 해석

옛날에 혼자 공부를 하면서 소수 구하기에 대해서 문제를 풀었던 적이 있다. 브루트 포스로도 풀 수 있지만, 양이 방대해지면 에라토스테네스의 체를 이용하여 풀어야 한다는 사실을 알고있다. 에라토스테네스의 체로 총 입력 받는 숫자의 범위인 1000000까지 소수를 구하고 그 소수들을 이용하여 짝수의 수를 소수들의 합으로 표현해주게끔 출력해주면 문제는 쉽게 풀 수 있다.

에라토스테네스의 체

Sieve_of_Eratosthenes_animation

우리가 알고 있는 소수중에 2의 배수들과 3의 배수들을 지워준다.
여기서 문제에서 나오는 범위인 1000000의 배수까지 지울 필요가 없다. 1000000의 제곱근인 1000의 배수까지만 지워주면 된다.
처음에 2의 배수들을 지우고, 3의 배수들을 지우고 나면 안지워진 숫자들을 찾아서 그 수를 소수로 인정해주고 그 수의 배수들을 다시 지워나가는 식으로 하면 소수들만 남게 된다.

풀이

에라토스테네스의 체를 10000000까지의 소수들을 list에 넣어주고 이중 루프를 돌면서 테스트 케이스로 입력 받은 수를 만드는 작업을 한다.
예를들어 테스트 케이스는 짝수이기 때문에 만드려면 홀수인 소수 두개가 필요하다. 그래서 2는 제외하고 시작한다.
맨 처음 루프에서는 3으로 시작하고 다음 루프에서는 3부터 쭉 탐색을 한다. 그래서 두 수를 더했을 때 테스트 케이스와 같은게 나오면 출력을 해주고 break로 이중 루프 전체를 빠져나간다.
만약 두 수의 합이 테스트 케이스를 넘어간다면 맨 처음 수를 그 다음 소수로 정해주고 다시 루프를 돌린다.

import sys

list = [True] * 1000001
list[0] = False
list[1] = False

prime = []

for i in range(2, 1000001):
    if i == 2:
        continue
    if list[i]:
        prime.append(i)
    for j in range(i * 2, 1000001, i):
        list[j] = False

while True:
    flag = 0
    T = int(sys.stdin.readline())
    if T == 0:
        break
    else:
        for i in prime:
            for j in prime:
                if i + j == T:
                    ans = str(T) + " = " + str(i) + " + " + str(j)
                    print(ans)
                    flag = 1
                    break
                elif i + j > T:
                    break
            if flag == 1:
                break
            elif i == prime[len(prime) - 1]:
                print("Goldbach's conjecture is wrong.")