풀이

먼저 주어진 n보다 작거나 같은 소수들을 리스트로 만들어주고 투포인터로 찾아주면 간단하게 풀린다.

import sys
from collections import deque

n = int(input())

def prime_sieve(n):
    sieve = [True] * (n+1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(n**0.5)+1):
        if sieve[i]:
            for j in range(i*i, n+1, i):
                sieve[j] = False
    primes = [i for i in range(2, n+1) if sieve[i]]
    return primes


def c(lst, target):
    right = 0
    left = 0
    count = 0
    sum = 0
    while right <= len(lst):
        if sum == target:
            count +=1
            sum -= lst[left]
            left += 1
        elif sum < target :
            if right == len(lst):
                break
            sum += lst[right]
            right += 1
        elif sum > target:
            sum -= lst[left]
            left +=1

    return count
lst = prime_sieve(n)
print(c(lst, n))