TCS CodeVita 2016 Round1 Question: Consecutive Prime Sum

Problem : Consecutive Prime Sum

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.

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:

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