<백준> 1644번 파이썬 알고리즘

N = int(input())

#에라토스테네스의 체 
arr = [False, False] + [True] * (N - 1)
prime = []
for i in range(2, N + 1):
    if arr[i] == True:
        prime.append(i)
        for j in range(i+i, N + 1, i):
            arr[j] = False
            
l = 0
r = 1
res = 0
while r <= len(prime):
    tmp = sum(prime[l:r])
    if tmp == N:
        res += 1
        r += 1
    elif tmp < N:
        r += 1
    else:
        l += 1
print(res)