백준 9020 골드바흐의 추측 (Python)

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

9020번: 골드바흐의 추측

소수 문제이기 때문에 당연하게 에라토스테네스의 체를 사용해서 소수를 먼저 구한 후 시작하였다.

 

그 후 입력마다, 해당 수를 반으로 나누고 반으로 나눈 값들에 1부터 더하거나 빼가며 둘 다 소수라면 반복문을 멈추고 출력하도록 했다.

import sys

T = int(sys.stdin.readline().strip())

prime = [True for _ in range(10001)]

for i in range(2, int(10001 ** 0.5) + 1):
    if prime[i]:
        for t in range(i + 1, 10001):
            if t % i == 0:
                prime[t] = False

for _ in range(T):
    n = int(sys.stdin.readline().strip())

    for i in range(n // 2 + 1):
        if prime[n // 2 - i] and prime[n // 2 + i]:
            print(n // 2 - i, n // 2 + i)
            break