난이도 : 골드 3
유형 : 투 포인터
https://www.acmicpc.net/problem/1644

문제 접근

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다.
몇 가지 자연수의 예를 들어 보면 다음과 같다.

3 : 3 (한 가지)
41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
53 : 5+7+11+13+17 = 53 (두 가지)
하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다.
7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

-> 소수는 중복해서 사용할 수 없다.
-> 소수는 연속되어야 한다.

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

핵심 아이디어

소수? -> 에라토스테네스의 체 떠올려야한다.

이전에 에라토스테네스의 체에 관해 포스팅했던게 있었다.

1. N 이하의 소수를 모두 구한다
   → 에라토스테네스의 체 사용 (O(N log log N))

2. 소수 배열에 대해 투 포인터로 합을 계산한다
   → 연속된 구간의 합이 N이 되는 경우의 수를 센다. (O(N))

해답 및 풀이

import sys
input = sys.stdin.readline

N = int(input())

def get_primes(N):
    is_prime = [True] * (N + 1) # 0~n까지 전부 소수(True)라고 가정
    is_prime[0] = is_prime[1] = False # 0과 1은 소수가 아님

    for i in range(2,int(N**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, N + 1, i): # i*i 부터 시작하는 이유는 중복을 건너뛰고 처리하기 위함이다. 이게 이해가 안간다면 에라토스테네스의 체 에 대해 다시 공부해보자.
                is_prime[j] = False

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

if N < 2:
    print(0)
    exit()

primes = get_primes(N)

start , end = 0, 0
count = 0
current_sum = 0

while True:
    if current_sum >= N: # 합이 N보다 크거나 같으면 → 왼쪽 포인터를 줄여서 합을 감소시킴
        if current_sum == N: # 합이 딱 N이면 정답 +1
            count += 1
        current_sum -= primes[start]
        start += 1
    
    elif end == len(primes): # end가 범위를 넘어서면 끝냄 (더 이상 확장 불가)
        break

    else: # 합이 N보다 작으면 → 오른쪽 포인터를 한 칸 늘려서 더해줌
        current_sum += primes[end]
        end += 1

print(count)