소수의 연속합

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

"""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()

• Dependency: teflib.numtheory.prime_list