Some prime numbers can be expressed as a sum of other consecutive prime numbers. For example 5 = 2 + 3, 17 = 2 + 3 + 5 + 7, 41 = 2 + 3 + 5 + 7 + 11 + 13. Now the 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.
Input Format:
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.
Constraints:
2<N<=12,000,000,000
Sample Input 1 :
20
Sample Output 1 :
2
Explanation :
5 = 2+3
17 = 2+3+5+7
Sample Input 2 :
15
Sample Output 2 :
1
Explanation :
5 = 2+3
Solution: In C
Solution: In Java
Solution: In Python 3
Also Checkout