[백준/Python] 1644번: 소수의 연속합

문제

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

1644번: 소수의 연속합

---

문제 요약

자연수 N이 주어졌을 때, 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.
 
ex)
3 = 3 => 한 가지
41 = 2 + 3 + 5 + 7 + 11 + 13 = 11 + 13 + 17 = 41 => 세 가지

---

코드

import math

n = int(input())

# 체 알고리즘을 이용하여 소수로 구성된 리스트 구하기

pri_arr = [True for _ in range(n + 1)] # n 까지 소수인지 아닌지를 판별하는 리스트 (초기: 소수 = True)

for i in range(2, int(math.sqrt(n) + 1)): # 2부터 n의 제곱근까지 모든 수를 확인
    if pri_arr[i] == True: # 아직까지 소수가 아닌 것으로 판별되지 않은 경우
        
        # i의 배수에 해당하는 값을 모두 소수가 아닌 것(False)으로 변경
        j = 2
        while i * j <= n:
            pri_arr[i * j] = False 
            j += 1

arr = [] # n까지의 모든 소수를 저장하는 리스트

for i in range(2, n + 1):
    if pri_arr[i]:
        arr.append(i)

ans = 0

# 투 포인터 방식으로 연속된 소수의 합으로 나타낼 수 있는 경우의 수 탐색
left = 0
right = 0

while right <=len(arr): # 오른쪽 포인터가 arr의 인덱스를 벗어나면 종료
    
    # 이번 탐색에서 투포인터가 가리키는 범위 left ~ right 인덱스에 해당하는 연속된 소수의 합
    tmp_sum = sum(arr[left:right]) 

    if tmp_sum == n: # n 이면
        ans += 1 # 경우의 수 증가

        # 다음 탐색을 위한 투포인터의 범위 이동
        left += 1
        right += 1 
    elif tmp_sum < n: # n보다 작으면
        right += 1 # 다음 탐색을 위한 투포인터의 범위 증가
    else:
        left += 1 # 다음 탐색을 위한 투포인터의 범위 감소

print(ans)

---

코드 설명

1. 체 알고리즘을 통해 n 이하의 자연수 중 소수인 자연수들로 구성된 리스트 arr을 생성한다.
 
< 체 알고리즘을 사용하지 않고 n이 소수인지 아닌지 구별하는 방법 >
- n을 2보다 크고 n보다 같거나 작은 모든 자연수로 나눠 나머지가 0인 경우가 없다면 소수이다.
 
=> 시간 초과가 발생한다.
 
< 체 알고리즘을 사용하여 n이 소수인지 아닌지 구별하는 방법 >
- n까지 소수인지 아닌지를 판별하는 크기 n + 1의 Boolean형 배열 pri_arr을 생성한다. (0 ~ n)
- 배열의 초기값은 모두 소수라고 생각한다. (True)
- 2부터 n의 제곱근까지 모든 수 i에 대해 i의 배수에 해당하는 모든 값을 소수가 아니라고 체크한다. (False)
- 위 과정을 수행했을 때, pri_arr[n]이 True라면 소수, 도중에 변경되어 False라면 소수가 아니다.
 
=> n 뿐만 아니라 n이하의 값까지 소수인지 아닌지 한 번에 알 수 있으므로 시간 초과가 발생하지 않는다.
 
2. 투포인터 탐색 알고리즘을 이용하여 arr연속된 소수의 합으로 나타낼 수 있는 경우의 수를 탐색한다.
+ left, right 포인터를 조건에 맞게 이동시키며 범위를 변경한다. 
 
3. 탐색에서 찾은 경우의 수를 출력한다.