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

문제

백준 - 1644번: 소수의 연속합

분석

N이 주어졌을 때 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제이다.

모두 더했을 때 N이 되는 것이므로 연속된 소수중에 N이 넘어가는 것은 있을 수가 없다. 따라서 1부터 N까지 소수가 될 수 있는 것을 에라토스테네스의 체로 걸러준다.

이렇게 연속된 소수를 배열로 가지고, 투 포인터를 적용해서 연속된 소수합이 N이 되는 경우의 수를 구하면 된다.

에라토스테네스는 2부터 N까지 모든 수 중에서 처리하지 않은 가장 작은 i를 찾고, i를 제외한 i의 배수를 모두 제거한다. 그런데 소수 판별은 N의 제곱근까지만 해도 된다. (대칭되는 값들이 이미 검증되어서 제곱근 이후의 수 부터는 확인이 무의미)

소수 배열들에서 i와 j포인터를 가지고 s가 n이 넘지 않을때까지 s에 누적시키고 j를 전진한다. j의 전진이 멈췄을 때 s가 n이 됐다면 경우의 수 cnt를 하나 증가한다.
s에서 현재 젤 앞에서 더해진 arr[i]를 빼주고 다음 i를 참고한다. 이 과정을 i가 소수 배열끝까지 도달할 때까지 진행한다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

import math
n = int(input())
prime = [True]*(n+1)

for i in range(2, int(math.sqrt(n))+1):
    if prime[i]:
        j = 2
        while i*j <= n:
            prime[i*j] = False
            j += 1
arr = []
for i in range(2, n+1):
    if prime[i]:
        arr.append(i)

j = 0
s = 0
cnt = 0
for i in range(len(arr)):
    while j < len(arr) and s < n:
        s += arr[j]
        j += 1
    if s == n:
        cnt += 1
    s -= arr[i]
print(cnt)

끝으로..

소수를 빠르게 구하는 에라토스테네스의 체에 대해 배운 점이 좋았고,
그것에 투 포인터를 결합한 응용문제를 풀어볼 수 있었다.