숫자 n을 입력받고 합이 n을 이루는 소수 a, b를 구한다. 두 소수 a, b를 찾았다면 "n = a + b"를 출력한다. (26~33번째 줄)
두 소수 a, b를 찾지 못했다면 "Goldbach's conjecture is wrong."을 출력한다. (35~36번째 줄)
이 문제가 생각보다 까다로운 점은 시간 초과에 있다.
여러 가지 이유로 시간 초과가 날 수 있는데, 내가 제거한 시간 초과 요인들은 다음과 같다. (여기를 참고)
에라토스테네스의 체
에라토스테네스의 체는 주어진 수 n까지 선형 탐색을 통해 모든 수에 대해서 소수 판별을 한다. 따라서 숫자를 입력받을 때마다 에라토스테네스의 체를 사용할 필요가 없이 입력값의 경계인 1000000을 포함하는 범위, 즉 1000001까지 한 번만 사용하면 된다. (18번째 줄)
소수 판정 범위
숫자 n의 소수 판정을 위해서 2부터 차례대로 n까지 나눗셈을 할 필요가 없다. n까지 나눗셈을 할 경우 O(n^2)의 시간 복잡도가 나오게 된다. sqrt(n)까지만 나누어줘도 소수 판정을 할 수 있다 (9번째 줄)
소수의 조합
합이 n인 두 소수 a, b를 구하기 위해 에라토스테네스의 체로 구한 소수들의 모든 조합을 구할 필요가 없다. 모든 조합을 구할 경우 O(n^2)의 시간 복잡도가 나오게 된다. n = a + b를 활용하여 선형 시간 안에 두 소수 a, b의 조합을 구할 수 있다. (28~30번째 줄)
import sys
from math import sqrt
# implementation of Sieve of Eratosthenes
def eratosthenes(n):
sieve = [True for _ in range(n)]
for i in range(2, int(sqrt(n)) + 1):
if sieve[i]:
for j in range(i * i, n, i):
sieve[j] = False
return sieve
# run only once
prime_list = eratosthenes(1000001)
while True:
n = int(sys.stdin.readline())
if n == 0:
break
found = False
# for linear search
for a in range(2, 1000001):
if prime_list[a]:
b = n - a
if prime_list[b]:
found = True
print("{0} = {1} + {2}".format(n, a, b))
break
if not found:
print("Goldbach's conjecture is wrong.")
