[백준] 17103 : 골드바흐 파티션 (Python/파이썬)

문제 링크

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

문제

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

입력

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

출력

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

예제

입력

5
6
8
10
12
100

출력

1
1
2
1
6

---

정답 및 풀이

import sys
input = sys.stdin.readline

MAX = 1000000
is_prime = [True] * (MAX + 1)
is_prime[0] = is_prime[1] = False

for i in range(2, int(MAX ** 0.5) + 1):
    if is_prime[i]:
        for j in range(i * i, MAX + 1, i):
            is_prime[j] = False

t = int(input())

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

    for a in range(2, n // 2 + 1):
        if is_prime[a] and is_prime[n - a]:
            cnt += 1

    print(cnt)

1. import sys
   • sys 모듈을 불러와 빠른 입력을 사용할 준비를 한다.
2. input = sys.stdin.readline
   • 기본 input() 대신 더 빠른 입력 방식을 사용한다. 많은 입력을 처리할 때 속도 향상에 효과적이다.
3. MAX = 1000000
   • 문제에서 가능한 n의 최댓값이 1,000,000이므로 소수 판별 범위를 설정한다.
4. is_prime = [True] * (MAX + 1)
   • 숫자 인덱스에 맞춰 소수 여부를 저장할 리스트를 만든다.
5. is_prime[0] = is_prime[1] = False
   • 0과 1은 소수가 아니므로 False로 설정한다.
6. for i in range(2, int(MAX ** 0.5) + 1):
   • 에라토스테네스의 체를 적용하기 위해 2부터 √MAX까지 반복한다.
7. if is_prime[i]:
   • i가 아직 소수로 남아 있다면 그 배수들을 제거해야 한다.
8. for j in range(i * i, MAX + 1, i):
   • i의 배수들을 모두 False로 표시한다. i*i부터 시작하는 이유는 그 이전 배수는 이미 처리되었기 때문이다.
9. is_prime[j] = False
   • j는 소수가 아니므로 False로 설정한다.
10. t = int(input())
    • 테스트 케이스의 개수를 입력받는다.
11. for _ in range(t):
    • t개의 테스트 케이스만큼 반복한다.
12. n = int(input())
    • 골드바흐 파티션을 구할 짝수 n을 입력받는다.
13. cnt = 0
    • 가능한 소수 쌍의 개수를 세기 위한 변수다.
14. for a in range(2, n // 2 + 1):
    • a를 2부터 n/2까지 확인한다. a ≤ b 조건을 만족하고 중복을 피하기 위한 핵심이다.
15. if is_prime[a] and is_prime[n - a]:
    • a와 b = n - a가 둘 다 소수라면 골드바흐 파티션이다.
16. cnt += 1
    • 조건을 만족하는 소수 쌍을 찾았으므로 개수를 증가시킨다.
17. print(cnt)
    • 해당 n에서 가능한 골드바흐 파티션의 총 개수를 출력한다.

---

새롭게 배운 내용 및 느낀점

• a ≤ b 조건을 기반으로 n/2까지만 탐색
  • 중복 없이 정확한 소수 쌍 개수를 세기 위한 핵심.