[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++

sql

닫기 줄바꿈

# 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