[BOJ][python] 9020. 골드바흐의 추측

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

9020번: 골드바흐의 추측

---

💡IDEA

수학의 소수를 사용하는 문제이다.

2022.07.21 - [Algorithm/BOJ] - [BOJ][python] 6588. 골드바흐의 추측

[BOJ][python] 6588. 골드바흐의 추측

6588번 문제와 거의 유사하지만, 이 문제에서는 골드바흐 파티션을 이루는 두 소수의 차가 가장 작은 것을 출력해야 한다.

먼저 소수인 수를 구하는 에라토스테네스의 체 방법을 사용하여 prime 배열을 설정한다.

prime 배열을 가운데서부터 처음까지 탐색하면 두 소수의 차가 가장 작도록 할 수 있다.

 

📌CODE

T = int(input())

prime = [1] * (10000 + 1)
prime[0] = 0
prime[1] = 0
m = int(10000 ** 0.5)
for i in range(2, m + 1):
    if prime[i]:
        for j in range(2 * i, 10000 + 1, i):
            prime[j] = 0

for _ in range(T):
    n = int(input())
    for i in range(n//2, -1, -1):
        if prime[i] and prime[n-i]:
            print(i, n-i)
            break