[BOJ/Step9] 9020 : 골드바흐의 추측 (Python)

www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

---

바로 전 문제에서 배운대로.. 미리 범위만큼 수를 소수 판별하고 시작 ㅎㅎ

입력받은 n을 반으로 나눠 하나씩 증가, 감소 하면서 둘 다 소수인 경우를 찾으면 둘 사이의 차가 가장 적어진다

1. 입력받은 t만큼 for문 반복

2. n을 입력받고 n의 반을 a와 b에 저장

3. a와 b가 둘 다 소수일 때만 a, b를 출력, 소수가 아니면 a--, b++

# 9020.py

N = 10001

prime = [False, False] + [True] * (N - 1)
for i in range(2, int(pow(N, 0.5) + 1)):
    if prime[i]:
        for j in range(i * i, N + 1, i):
            prime[j] = False

t = int(input())

for i in range(t):
    n = int(input())
    a = n // 2
    b = n // 2
    while True:
        if prime[a] and prime[b]:
            print(a, b)
            break
        else:
            a -= 1
            b += 1