[BOJ] 9020 골드바흐의 추측

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

이 문제도 4948 베르트랑 공준에서 사용했던 에라토스테네의 체를 사용하면 될 것 같다. 먼저 소수를 구한 뒤, 골드바흐 파티션을 구해야 하므로 배열을 소수만 가진 배열로 바꿔준다. 이후 소수의 합으로 구해질 수 있는 것 중 차이가 가장 작은 것을 출력한다.

t = int(input())
inputs = []
for _ in range(t):
    n = int(input())
    inputs.append(n)
n_max = max(inputs)

# 일단 소수를 구하자
arr = [False, False] + [True] * (n_max - 1)
for i in range(2, n_max+1):
    if arr[i]:
        for j in range(i*2, n_max+1, i):
            arr[j] = False

# 파티션을 구하자
arr = [i for i, el in enumerate(arr) if el]
for n in inputs:
    gap = n
    for i in arr:
        if n-i in arr:
            if gap > abs(n-i*2):
                a = i
                b = n-i
                gap = abs(n-i*2)
    print(a, b)