[백준] 17103번 골드바흐 파티션 - Python / 알고리즘 기초 1/2 - 수학 1 (연습)

---

---

---

💡 문제

• 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

출력

각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

---

💭 접근

6588번 골드바흐의 추측 문제와 비슷한 문제이다.

1. 에라토스테네스의 체 알고리즘을 이용하여 최대범위 (1,000,000)까지의 소수를 구한다.
2. 이후 입력 n의 n//2까지 반복하며 골드바흐의 추측을 만족하는 수의 개수를 찾는다.

---

📒 코드

def seive_of_eratosthenes(n):
    is_prime = [False] * 2 + [True] * (n - 1)
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i**2, n + 1, i):
                is_prime[j] = False
    return is_prime

prime = seive_of_eratosthenes(1000000)

t = int(input())
for _ in range(t):
    n = int(input())

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

---

💭 후기

이전 6588번 골드바흐의 추측 문제와 거의 똑같은 문제라서 쉽게 해결했다.

---

🔗 문제 출처

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

---