풀이 1. 에라토스테네스의 체(시간 : 96ms)

import sys
input = sys.stdin.readline

num = 10000

is_prime = [False, False] + [True]*(num-1)
for i in range(2, num + 1):
    if is_prime[i] == True:
        for j in range(i * 2, num+1, i):
            is_prime[j] = False

repeat = int(input())

for i in range(repeat):
    n = int(input())
    half = n//2

    for j in range(half, 1, -1):
        if is_prime[j] == True and is_prime[n-j] == True:
            print(j, n - j)
            break

풀이 2. 기본적인 소수 찾기(시간: 3616ms)

import sys
input = sys.stdin.readline

def is_prime(a: int) -> bool:
    if a % 2 == 0:  # 짝수이므로
        return False

    for i in range(2, a):
        if a % i == 0:
            return False
    
    return True

def find(n: int) -> list:
    half = n//2

    for i in range(half, 1, -1):
        if is_prime(i) and is_prime(n-i):
            break
    print(i, n-i) 

N = int(input())

for i in range(N):
    a = int(input())
    find(a)

풀이 3. 소수 판별 시 범위 제곱근까지 줄이기(시간: 196ms)

import sys
input = sys.stdin.readline

def is_prime(a: int) -> bool:
    if a % 2 == 0:  # 짝수이므로
        return False

    sqr = int(a**(1/2))

    for i in range(2, sqr + 1):
        if a % i == 0:
            return False
    
    return True

def find(n: int) -> list:
    half = n//2

    for i in range(half, 1, -1):
        if is_prime(i) and is_prime(n-i):
            break
    print(i, n-i) 

N = int(input())

for i in range(N):
    a = int(input())
    find(a)