[백준] 17103번 : 골드바흐 파티션 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

1. 문제 섦

 

17103번: 골드바흐 파티션

 

1. 문제 설명

2. 풀이과정

해당 문제는 수의 골드바흐 파티션 개수를 구하는 문제이다.

골드바흐 파티션을 파악하려면 수의 합을 이루는 2개의 숫자가 모두 소수이어야 한다.

여기서 수의 최댓값이 1,000,000이므로 범위가 크다.

해당 범위의 수까지 소수를 판별하려면 많은 시간이 소요되기 때문에 해당 문제에서는 "에라토스테네스의 체" 방법을 활용하여 해당 범위 안의 소수를 구한다.

"에라토스테네스의 체"는 제일 작은 소수인 2부터 해당 수의 배수를 모두 제거하고, 남아 있는 수 중 그다음 소수로 넘어간다. 다음 소수의 배수도 모두 제거한다. 이렇게 범위의 끝까지 해당 소수의 배수를 제거하며 소수를 찾는 방법이다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 각 수가 소수인지 판별할 리스트를 생성한다. li = list(True for _ in range(1000001))
3. 0과 1은 소수가 아니므로 False로 변경해 준다. li[0] = False  li[1] = False
4. 제일 작은 소수인 2부터 1000000까지 수를 불러오며 for i in range(2, 1000001)
5. 만약 해당 수가 소수이면 if li[i]
6. 해당 소수의 배수는 소수가 아니므로 for j in range(i * 2, 1000001, i)
7. False로 변경해 준다. li[j] = False
8. 테스트 케이스의 횟수를 입력받고 T = int(sys.stdin.readline())
9. 테스트 케이스 횟수만큼 반복하며 for _ in range(T)
10. 정수를 입력받는다. N = int(sys.stdin.readline())
11. 골드바흐 파티션의 개수를 저장할 변수를 생성하고 초기화한다. count = 0
12. 제일 작은 소수인 2부터 해당 수의 절반까지 반복하며 for i in range(2, N // 2 + 1)
13. 만약 해당 수와 그 합이 되는 수가 모두 소수이면 if (li[i] and li[N - i])
14. 골드바흐 파티션의 개수를 1 증가시킨다. count += 1
15. 가능한 합을 모두 판별했으면 골드바흐 파티션의 개수를 출력한다. print(count)

반응형

3. 소스코드

import sys

li = list(True for _ in range(1000001))
li[0] = False
li[1] = False
for i in range(2, 1000001):
    if li[i]:
        for j in range(i * 2, 1000001, i):
            li[j] = False
        
T = int(sys.stdin.readline())

for _ in range(T):
    N = int(sys.stdin.readline())
    
    count = 0
    for i in range(2, N // 2 + 1):
        if (li[i] and li[N - i]):
            count += 1
            
    print(count)