Some prime numbers can be expressed as Sum of other consecutive prime numbers.

For example

5 = 2 + 3

17 = 2 + 3 + 5 + 7

41 = 2 + 3 + 5 + 7 + 11 + 13

Your task is to find out how many prime numbers which satisfy this property are present in the range 3 to N subject to a constraint that summation should always start with number 2.

Write code to find out number of prime numbers that satisfy the above mentioned property in a given range.

For example

5 = 2 + 3

17 = 2 + 3 + 5 + 7

41 = 2 + 3 + 5 + 7 + 11 + 13

Your task is to find out how many prime numbers which satisfy this property are present in the range 3 to N subject to a constraint that summation should always start with number 2.

Write code to find out number of prime numbers that satisfy the above mentioned property in a given range.

Input Format:

First line contains a number N

First line contains a number N

Output Format:

Print the total number of all such prime numbers which are less than or equal to N.

Print the total number of all such prime numbers which are less than or equal to N.

Constraints:

1. 2

Sample Input and Output

SNo. | Input | Output | Comment |
---|---|---|---|

1 | 20 | 2 | (Below 20, there are 2 such numbers: 5 and 17). 5=2+3 17=2+3+5+7 |

2 | 15 | 1 |

Pseudo Code:

1. Find all the prime numbers till N

i. A is an array length N + 1 initialized with numbers from 0 to N (0,1,2, ..., N)

ii. initialize p = 2

a. for p = 2 to p * p <= N ; p++

if A[p] != 0 then

for i = p * 2; i <= N; i += p

A[i] = 0 // mark non prime as 0

2. sum = 5, count = 0

3. for j = 5 to j <= N; j = j+2

i. if ( (A[j] != 0 && A[j] = sum) || A[j] = -1)

count = count + 1

ii. if (A[j] != 0 || A[j] == -1)

sum = sum + j

if ( A[sum] != 0) // if A[sum] is prime

A[sum] = -1 // mark A[sum] as sum of consecutive

4. print count