백준: 6588 골드바흐의 추측

문제

6588번: 골드바흐의 추측

 

문제 풀이

 4 보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있는것이 크리스티안 골드바흐의 추측이다. 문제는 다음과 같은 순서에 따라 풀 수 있다.

 

1. 최대 입력되는 수는 100000이므로, 최대 입력 수 까지의 소수를 미리 계산한다.
2. 원래수 - 홀수인 소수 = 홀수 이므로, 가장 작은 홀수인 소수 부터 원래 수 - 홀수인 소수 모두 소수인지 판별하면 된다.
   • 예를 들어 8인 경우 가장 작은 홀수인 소수인 3을 통해 계산한 값은, 5(8 - 3)이므로 둘 다 소수여서 조건에 만족한다.
   • 이와 달리 42인 경우는 3, 39(42 - 3)은 만족하지 않고 그다음 홀수인 소수가 5이므로 5, 37(42 -5)가 조건을 만족하여 정답이 된다.
   • 출력은 두 수의 차가 가장 큰 것을 출력하므로 가장 작은 홀수인 3부터 증가하여 답을 찾으면 된다.
     • 최대 수인 100000이 입력된다고 하여도 11 + 99989로 정답을 만족하므로, 최초에 소수를 미리 계산하는 시간을 제외한다면 나머지는 경미할 것이다.
3. 파이썬에서는 `input`이 반복될 경우 시간이 오래걸리므로, `sys.stdin.readline`을 사용한다.

 

코드

from sys import stdin


def is_prime(n):
    nums = [True] * n
    for i in range(2, int(n ** 0.5) + 1):
        if nums[i]:
            for j in range(i + i, n, i):
                nums[j] = False
    return nums

if __name__ == '__main__':
    nums = is_prime(1000000)
    while True:
        n = int(stdin.readline())
        if not n:
            break
        for i in range(3, n // 2 + 1):
            if nums[i] and nums[n - i]:
                print("{} = {} + {}".format(n, i, n - i))
                break

 미리 소수를 체크해 두어 시간 초과가 발생하지 않으며, `input`을 사용하지 않고 `sys.stdin.readline`을 사용하여 시간은 320ms가 걸린다.