**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.

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

## No comments :

## Post a Comment