====== 소수의 연속합 ======

===== 풀이 =====
  * 소수들을 먼저 찾아서 리스트에 저장해두고 거기에서 합이 N이 되는 연속된 구간의 갯수를 찾으면 된다.
  * n이하의 소수들을 모두 찾는 것은 [[ps:소수 목록 구하기|에라토스테네스의 체]]를 이용해서 O(nloglogn)에 가능하다.
  * 배열에서 합이 Y가 되는 구간의 갯수를 세는 것은 [[ps:투 포인터]]를 이용하면 배열 길이에 비례하는 시간에 구할수 있다. n이하의 소수의 갯수는 O(n/logn)이므로, 이 작업의 시간복잡도는 O(n/logn)
  * 총 시간복잡도는 O(nloglogn)이 된다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1644. 소수의 연속합".

- Problem link: https://www.acmicpc.net/problem/1644
- Solution link: http://www.teferi.net/ps/problems/boj/1644

Tags: [Sieve] [TwoPointer]
"""

from teflib import numtheory


def main():
    N = int(input())

    primes = numtheory.prime_list(N)
    left_iter, right_iter = iter(primes), iter(primes)
    prime_sum = answer = 0
    while True:
        try:
            if prime_sum == N:
                answer += 1
            if prime_sum <= N:
                prime_sum += next(right_iter)
            else:
                prime_sum -= next(left_iter)
        except StopIteration:
            break

    print(answer)


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:numtheory#prime_list|teflib.numtheory.prime_list]]

{{tag>BOJ ps:problems:boj:골드_3}}