[Python] 백준 17103번: 골드바흐 파티션

SeungHyun·2024년 4월 27일

코딩테스트

coding test

목록 보기

15/16

0. 기본 정보

0-A. 개요

python/백준 - 17103번 문제에 대한 분석임.

0-B. 문제 정보

백준 - 17103번: 골드바흐 파티션

1. 정답 코드

isprime = [True] * 1000001
isprime[0:2] = [False, False]
for i in range(2, 1000001):
    if isprime[i]:
        for j in range(i * 2, len(isprime), i):
            isprime[j] = False
 
t = int(input())
 
for _ in range(t):
    n = int(input())
 
    count = 0
    for i in range(2, n // 2 + 1):
        if isprime[i] and isprime[n - i]:
            count += 1
 
    print(count)

2. 핵심풀이

에라토스테네스의 체를 활용한 멋진 풀이가 있어서 해당 글을 작성해본다.
1에서 서술한대로 에라토스테네스의 체를 활용한 풀이.

2-a. 코드 분석

isprime = [True] * 1000001
isprime[0:2] = [False, False]

에라토스테네스의 체를 구현하기 위한 초석이다.
- True: 소수
- False: 소수가 아닌 정수
- 0과 1은 소수가 아니기 때문에 False처리 해준다.

for i in range(2, 1000001):
    if isprime[i]:
        for j in range(i * 2, len(isprime), i):
            isprime[j] = False

실제 에라토스테네스의 체를 구현하는 부분
2부터 문제에서 제시하는 최대 정수인 1000000까지 하나씩 for문으로 돌린다.
이때 isprime[i]일 경우(소수일 경우) i보다 크며 i의 배수인 경우는 소수가 아니므로 전부 False처리 해준다. (에라토스테네스의 체)

t = int(input())
 
for _ in range(t):
    n = int(input())
 
    count = 0
    for i in range(2, n // 2 + 1):
        if isprime[i] and isprime[n - i]:
            count += 1
 
    print(count)

앞서 구현한 에라토스테네스의 체를 이용해서 골드바흐 파티션인지 확인하는 코드
if isprime[i] and isprime[n - i]: 이 부분이 핵심인데
isprime의 원소는 전부 bool 타입이지만 isprime의 index를 우리가 찾으려는 골드바흐 파티션인지를 확인하는 용도로 사용한다.
즉, i + (n - i)는 무조건 n이므로 isprime[i]와 isprime[n - i] 둘 다 참이라면 둘 다 소수란 의미이고 둘 다 소수란 의미는 두 소수의 합으로 나타낼 수 있다는 의미이므로 골드바흐 파티션임을 의미한다.