💡문제접근
- 에라토스테네스의 체를 이용하여 소수를 걸러준 다음 두 소수의 차이가 가장 작은 파티션을 출력한다. 이 때, 두 소수의 차이가 가장 작은 파티션을 출력하기 위해서 중간값을 기준으로 중간값을 이용해 조건에 맞는 값을 출력하도록 코드를 작성했다.
💡코드(메모리 : 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