백준 알고리즘 9020 (골드바흐의 추측) - python

[문제] 백준 알고리즘 9020 (골드바흐의 추측)

> https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

 

소수 조합의 합으로 모든 짝수를 만들 수 있다는 골드바흐의 추측을 활용한 문제이다.

그 중에서도 두 소수의 차이가 가장 적은 두 수를 출력하는 조건이다.

 

가장 먼저 든 생각은, 한 번에 여러 테스트 케이스가 주어지므로,

자연수 N<= 10000 에서의 소수를 미리 구해 놓고 조건에 맞는 출력만 하면 되겠다는 생각이었다.

따라서, 먼저는 에라토스테네스의 체를 이용하여 모든 소수를 구한다.

여기까지는 괜찮았는데, 여러 번의 시간 초과로 고생했다....

 

찾아낸 효율적인 방식은 다음과 같다.

주어지는 n이 짝수이므로, n의 절반도 자연수이고, 그 수가 소수라면 가장 이상적인 답일 것이다.

하지만 그 수가 소수가 아니라면, n의 절반에서 가까운 소수의 조합을 찾는 방법을 썼다.

(n의 절반 - x) + (n의 절반 + x) = n 이므로 x를 증가시키다 보면 맞는 소수가 나올 것이다.

 

[Code]

import sys
N = 10001
sieve = [True] * N
def prime_sieve(N):
    for i in range(2, N):
        if sieve[i]:
            for j in range(2*i, N, i):
                sieve[j] = False
prime_sieve(N)

T = int(sys.stdin.readline())
for _ in range(T):
    n = int(sys.stdin.readline())
    idx = 0
    while True:
        if sieve[n//2 - idx] and sieve[n//2 + idx]:
            print(n//2 - idx, n//2 + idx)
            break
        idx += 1