BOJ 9020 골드바흐의 추측

https://www.acmicpc.net/problem/9020
시간 2초, 메모리 256MB
input :

• 테스트 케이스의 개수 T
• 짝수 n(4 ≤ n ≤ 10,000)

output :

• 주어진 n의 골드바흐 파티션을 출력
• 출력하는 소수는 작은 것부터 먼저 출력

조건 :

• 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력

---

오옹 잊고 있었는데 출력하는 소수는 작은 것 부터 하라고 했었네;;

별거 없다 가능 한 모든 소수를 찾아서 n을 만들 수 있는지 확인 하면 된다.
i, n - i 둘 다 소수인지를 판 별 해주어야 한다.

import sys
from math import sqrt

prime_number = [1] * 10001
prime_number[0] = prime_number[1] = 0
for i in range(2, int(sqrt(10001))):
    for j in range(i * i, 10001, i):
        if prime_number[j]:
            prime_number[j] = 0


t = int(sys.stdin.readline())
for i in range(t):
    n = int(sys.stdin.readline())
    ret = []

    for j in range(2, n // 2 + 1):
        temp = n - j
        if prime_number[j] and prime_number[temp]:
            ret.append((j, n - j))
    print(ret[-1][0], ret[-1][1])