골드바흐의 추측 - 9020번

소수 범위 제한이 적으므로 먼저 아리스토테네스의 체를 만든다.

n을 입력 받을 때 미리 만들어둔 아리스토테네스의 체를 이용해 문제에 만족하는 두 소수를 구한다.

python3로 제출하면 9%에서 시간초과가 뜨는데, pypy3로 제출하면 4620ms로 성공한다.

좀더 시간을 줄여야 한다.

import sys
t = int(sys.stdin.readline())

prime = []
prime_bool_check = [True]*(10001)

for i in range(2,int(10001**(1/2))):
    for j in range(i*i, 10001, i):
        prime_bool_check[j] = False
for i in range(2, 10001):
    if prime_bool_check[i]:
        prime.append(i)

for _ in range(t):    
    n = int(sys.stdin.readline())
    ans = [n,n]
    mini = n
    cnt = 0
    for i in prime:
        if i > n:
            break
        for j in prime:
            if j > n:
                break
            if i+j == n and mini > abs(i-j):
                mini = abs(i-j)
                ans = [i,j]
    ans.sort()
    print(ans[0],ans[1])