골드바흐의 추측

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

문제 푸는 데 하루종일 걸렸다. 만만하게 봤다가 시간초과 무한루프 걸려서. oTL

문제 해결까지 몇 단계를 거쳐야 한다.

1. 1부터 정수 n까지 소수만 뽑아낸다.
2. 소수 중 합이 n이 되는 두 수를 걸러낸다.
3. 두 수 중 차(-)가 가장 큰 숫자를 오름차순으로 뽑는다.
4. 출력.

소수를 걸러내는 방법은 '에라토스테네스의 체'를 활용하면 된다. 두 수의 합이 n이 되는 소수도 어렵진 않다. 소수 중 두 개씩 묶은 순열(permutations)에서 합이 n이 되는 첫 번째 순열이 차가 가장 큰 순열이다.

그런데…

이렇게 구현하면 100% 시간초과에 걸린다. itertools 라이브러리의 permutations 함수를 써도 초과, for문을 돌려도 어김없이 초과, i in arr 식으로 내부탐색을 해도 초과. 게다가 n이 주어질 때마다 에라토스테네스의 체를 돌려도 시간 초과…

FAQ를 읽고 차근차근 조건에 맞춰 코드를 수정했다.

1. 에라토스테네스의 체는 처음 1번만 실행. n의 최대값이 1,000,000이니 100만을 기준으로 최초 1회 실행해 소수 리스트 생성.
2. for 문과 내부 탐색을 최대한 줄이기.
3. 각 소수를 하나씩 비교할 필요 없음. p 소수에 대해 n-p 값의 존재 여부만 확인하면 됨.
4. p와 n-p가 모두 1(true)일 경우 답을 출력하고 반복문 종료.

10여 차례 제출 끝에 겨우 성공했다. 오류는 그 10배는 나온 듯.

결과 코드는 아래와 같다.

import sys
def prime_list(n): # 에라토스테네스의 체를 응용해 소수 판별하기.
    prime = [1] * (n+1) # 주어진 숫자+1 만큼 1(True)로 채운 리스트(prime) 생성. 리스트 첫 인덱스가 0이기 때문.
    for i in range(2, int((n+1)**0.5)+1): # 2부터 sqrt(n+1)+1까지 탐색. 소수의 최대값은 sqrt(n)이니까.
        if prime[i] == 1: # 1이 나올 경우
            for j in range(i*2, n+1, i): # i의 다음 배수부터 끝까지 
                prime[j] = 0 # 값을 0(False)으로 변경
    return prime # [1, 1, 1, 1, 0, 1, 0, ...] prime[2:]부터 값이 1인 숫자의 인덱스 값이 소수임.
l = prime_list(1000000) # 에라토스테네스의 체를 이용해 소수 리스트 생성
while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    for i in range(3, n//2): # 3부터 시작. 0-2는 필요없으니. 
        if l[i] and l[n-i]: # i와 n-i가 모두 소수일 경우
            print(f"{n} = {i} + {n-i}")
            break

덧. 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.는 조건은 실제로 나올 수 없는 경우이므로 무시. :)

문제 보기