Consecutive Prime Sum

Interview

Time limit2sMemory limit128 MB

Summary

Count how many ways a given N up to 4,000,000 can be written as a sum of one or more consecutive prime numbers.

Level: Medium4 of 10
Topics: Sliding window, Two pointers, Number theory, Math
Solved: No attempts yet

Problem

Given a positive integer N, count the number of ways to represent N as the sum of one or more consecutive prime numbers.

Consecutive primes mean adjacent numbers in the increasing sequence of prime numbers. A prime number cannot be used more than once in a sum, and a sum that skips a prime in the middle is not considered a sum of consecutive primes.

Input

The first line contains a positive integer N. (1 <= N <= 4,000,000)

Output

Print the number of ways to represent N as the sum of consecutive prime numbers.

Examples4

Example 1
Input
```
20
```
Expected output
```
0
```
Example 2
Input
```
3
```
Expected output
```
1
```
Example 3
Input
```
41
```
Expected output
```
3
```
Example 4
Input
```
53
```
Expected output
```
2
```