백준 1644 소수의 연속

n = int(input())


prime = []
p = [True] * (n+1)
# n == 1 인 경우를 위해
if n == 1:
    prime = [0]
else:
    for i in range(2, n+1):
        if p[i]:
            prime.append(i)
        for j in range(2*i, n+1, i):
            p[j] = False 
cnt = 0
left = 0
right = 0
tmp_sum = prime[left]
l = len(prime)

loopout = False

while True:
    if tmp_sum > n:
        tmp_sum -= prime[left]
        left += 1
    elif tmp_sum == n:
        cnt += 1
        if left == right:
            right += 1
            if right == l or left > right:
                loopout = True
                break    
            tmp_sum += prime[right]
        else:
            tmp_sum -= prime[left]
            left += 1
    elif tmp_sum < n:
        right += 1
        if right == l or left > right:
            loopout = True
            break    
        tmp_sum += prime[right]
    if loopout:
        break

print(cnt)

처음에 n 이 1인 경우를 고려하지 않음
에라토스테네스 체 + 투포인터