Programming Geek
Rated 4.7/5 based on 1446 reviews  ### 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.InputOutputComment
1202
(Below 20, there are 2 such numbers: 5 and 17).
5=2+3
17=2+3+5+7
2151

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