문제 출처 : https://www.acmicpc.net/problem/1644
난이도 : 골드 3

문제 파악

문제: N을 ‘연속된 소수들의 합’으로 만들 수 있는 경우의 수를 구해야 한다.
(예: 41 = 2+3+5+7+11+13 = 11+13+17 = 41 → 3가지

“연속된 소수”라는 말이 핵심이다.
→ 소수들을 정렬된 리스트로 뽑아놓으면, 그 리스트에서 연속 부분 구간의 합을 보는 문제로 바뀐다.

그리고 소수는 전부 양수다.
→ 연속 부분합 문제에서 양수만 있으면 투 포인터(슬라이딩 윈도우)로 풀 수 있다.

부분 합 문제 에 소수를 판별하는 에라토스테네스의 체 를 결합한 문제이다.

해결 로직

1) N 이하 소수 리스트 만들기 (에라토스테네스의 체)
2) primes 위에서 투 포인터로 적절한 “연속합 = N” 개수를 세기.

해답 및 풀이

import sys
input = sys.stdin.readline

N = int(input().strip())

# 예외: 1은 어떤 소수의 연속합으로도 만들 수 없다.
if N < 2:
    print(0)
    sys.exit()

# 1) 에라토스테네스의 체로 N 이하 소수 리스트 만들기
is_prime = [True] * (N + 1)
is_prime[0] = is_prime[1] = False

for i in range(2, int(N ** 0.5) + 1):
    if is_prime[i]:
        # i의 배수들을 전부 소수 아님 처리
        for j in range(i * i, N + 1, i):
            is_prime[j] = False

primes = [i for i in range(2, N + 1) if is_prime[i]]

# 2) primes 위에서 투 포인터로 연속합이 N 되는 경우의 수 세기
left = 0
right = 0
total = 0
answer = 0

while True:
    if total >= N:
        # 현재 합이 이미 N 이상이면 창을 줄여야 한다.
        if total == N:
            answer += 1
        total -= primes[left]
        left += 1
    else:
        # total < N이면 창을 늘려야 한다.
        if right == len(primes):
            break
        total += primes[right]
        right += 1

print(answer)