# [TCS] CodeVita Problem : Consecutive Prime Sum C-language Program

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

TCS CodeVita 2016 Round1 Question: Consecutive Prime Sum
C-Language Program (MockVita1/consecprimesum.c)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef long int ulint;

bool isPrime(ulint);
bool isConsecSumPrime(ulint, ulint*);

ulint* buildPrimesList(ulint n)
{
ulint i;
ulint* vals = (ulint*) malloc(sizeof(ulint) * n);+
vals = vals = 2;

for (i = 3; i < n; i += 2)
if (isPrime(i))
vals[vals++] = i;

return vals;
}

int main()
{
ulint* primes;
ulint n;
int i, c = 0;

scanf("%ld", &n);
primes = buildPrimesList(n);

for (i = 2; i < primes; i++)
if (isConsecSumPrime(primes[i], primes))
c++;

printf("%ld", c);
free(primes);

return 0;
}

bool isPrime(ulint n)
{
ulint i, w;

if (n == 2) return true;
if (n == 3) return true;
if (n % 2 == 0) return false;
if (n % 3 == 0) return false;

i = 5, w = 2;

while (i * i <= n)
{
if (n % i == 0)
return false;

i += w;
w = 6 - w;
}

return true;
}

bool isConsecSumPrime(ulint prime, ulint* primes)
{
int n;
ulint sum = 0;

for (n = 1; n < primes; n++)
{
sum += primes[n];

if (sum == prime)
return true;

if (sum > prime)
return false;
}

return false;

}

Sources:
https://www.programminggeek.in/
https://github.com/

* Ask us, what you want?