[백준] 9020번 골드바흐의 추측

💡문제접근

• 에라토스테네스의 체를 이용하여 소수를 걸러준 다음 두 소수의 차이가 가장 작은 파티션을 출력한다. 이 때, 두 소수의 차이가 가장 작은 파티션을 출력하기 위해서 중간값을 기준으로 중간값을 이용해 조건에 맞는 값을 출력하도록 코드를 작성했다.

💡코드(메모리 : 30728KB, 시간 : 3532ms)

import sys
input = sys.stdin.readline

def sieve_of_Eratosthenes(n):
    arr = [True for _ in range(n+1)]
    arr[0] = False
    arr[1] = False
    for i in range(2, int(n**0.5)+1):
        if arr[i]:
            for j in range(2*i, n+1, i):
                arr[j] = False
    return [i for i in range(2, n+1) if arr[i]]


T = int(input())
for _ in range(T):
    n = int(input())
    li = sieve_of_Eratosthenes(n)
    a = n // 2
    while a > 0:
        if a in li and n - a in li:
            print(a, n-a)
            break
        a -= 1

💡소요시간 : 1h 11m