Saturday, July 14, 2018

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

Problem : Consecutive Prime Sum

www.matterhere.com - Nareddula Rajeev Reddy (NRR)


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[0] = vals[1] = 2;

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

    return vals;
}

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

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

    for (i = 2; i < primes[0]; 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[0]; 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?
EmoticonEmoticon