[백준] 9020 : 골드바흐의 추측

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

9020번: 골드바흐의 추측

---

• 1부터 10000까지 존재하는 소수들을 에라토스테네스의 체를 사용하여 모두 구해준다. (약 1200개)
• 골드바흐 파티션을 정할 때, 1~10000 까지 각 짝수마다 가능한 소수 조합을 전부 돌려보기에는 10000 * 1200(소수1) * 1200(소수2) 번의 연산이 필요하므로 시간초과가 발생한다.
• 소수1 과 소수2 를 전부 탐색하는 과정에서, 두 소수로 짝수가 만들어지면 해당 수의 골드바흐 파티션으로 지정해준다.
• 소수1 이 항상 소수2 보다 작게끔 탐색을 돌린다면 여러 파티션들 중 가장 가까운 파티션이 최종적으로 할당된다.

---

import sys

rn = [True for i in range(10001)]
prime = []
pt = [(0,0) for i in range(20000)]

# 에라토스테네스의 체로 10000 이하의 모든 소수들 구함
for i in range(2, 10001):
    if rn[i]:
        prime.append(i)
        tmp = i + i
        while tmp <= 10000:
            rn[tmp] = False
            tmp += i

# 모든 조합을 살펴보며 골드바흐 파티션을 구함
for i1 in range(len(prime)):
    for i2 in range(i1, len(prime)):
        # 첫번째 수와 두번째 수를 뽑아 가능한 값들에 해당 쌍을 저장
        # 여러 쌍이 있을 경우 자연스럽게 뒤쪽에서 두 값이 더 가까운 쌍으로 갱신됨
        pt[prime[i1] + prime[i2]] = (prime[i1], prime[i2])

# 골드바흐 파티션을 메모이제이션 해놨으므로 답 출력
input()
for line in sys.stdin:
    line = int(line.strip())
    print(pt[line][0], pt[line][1])