📌 코드 작성

import sys, math

def get_primes(n):
    # 소수 판별을 위한 배열 초기화
    sieve = [True] * (n+1)
    sieve[0], sieve[1] = False, False
    
    # 에라토스테네스의 체 알고리즘
    # 2부터 sqrt(n)까지의 모든 수를 순회하면서,
    # 현재 수가 소수인 경우 그 수의 배수들을 전부 False로 변경한다.
    for i in range(2, int(math.sqrt(n))+1):
        if sieve[i]:
            for j in range(i+i, n+1, i):
                sieve[j] = False
    
    # 소수 리스트 구하기
    primes = []
    for i in range(2, n+1):
        if sieve[i]:
            primes.append(i)
    return primes

def goldbach_partition(n, primes):
    # 차이가 가장 작은 두 소수를 찾는 과정
    min_diff = sys.maxsize
    result = (0, 0)
    for p in primes:
        # 현재 소수가 n // 2보다 크면,
        # 그 이후의 소수들과 합으로 n을 나타낼 수 없다.
        if p > n // 2:
            break
        if n - p in primes:
            # 차이가 가장 작은 두 소수를 찾는다.
            if min_diff > n - 2 * p:
                min_diff = n - 2 * p
                result = (p, n - p)
    return result

# 1. 10000 이하의 소수 리스트 구하기
primes = get_primes(10000)

# 2. 골드바흐 파티션 구하기
for _ in range(int(input())):
    n = int(input())
    p1, p2 = goldbach_partition(n, primes)
    print(p1, p2, sep=' ')

해당 문제는 일단 내 취향은 아니다...
생각보다 역시 수학이 싫었던 나는 저런 공식이 있는 지도 몰랐음

📌 코드에 대한 설명

• get_primes(n) 함수는 에라토스테네스의 체 알고리즘을 사용하여 n 이하의 모든 소수를 찾아내는 함수입니다.
• goldbach_partition(n, primes) 함수는 입력값 n과 소수 리스트 primes를 받아서, n을 두 소수의 합으로 나타내는 가장 작은 차이를 가지는 두 소수를 찾아내는 함수입니다.
• 이를 위해서, primes 리스트에 있는 소수들을 작은 숫자부터 하나씩 확인하면서, n보다 작은 소수 p를 찾습니다.
• 이어서 n - p가 소수 리스트 primes에 있는지 확인합니다. 만약 존재한다면, p와 n - p를 합으로 나타내어 n을 만들 수 있으므로, 차이를 계산하여 기존의 값보다 작다면 이를 최소값으로 저장합니다.
• 마지막으로, get_primes(10000) 함수를 호출하여 10000 이하의 모든 소수를 구합니다.
• 이후, 입력값을 받아 goldbach_partition(n, primes) 함수를 호출하여 골드바흐 파티션을 구하고, 이를 출력합니다.
• print(p1, p2, sep=' ')에서 sep은 출력값 간의 구분자를 의미합니다. 여기서는 두 소수 간에 공백을 넣어 출력하도록 설정되어 있습니다.