### PROBLEM LINKS:

**Author:** Animesh Fatehpuria

**Testers:** Rajat De Sumit Shyamsukha

**Editorialist:** Animesh Fatehpuria

### DIFFICULTY:

SIMPLE

### PREREQUISITES:

### PROBLEM:

Given Two Numbers **M** and **N** , Find the Sum of Prime Numbers between **M** and **N** (inclusive).

Given **M<=5000000** and **N<=5000000**

### EXPLANATION:

## How To Get 30 Points:-

To get 30 points , using any function for checking whether a number is a Prime Number or not will work. A number is a Prime Number if the number of factors it has ( including 1 and itself) is TWO. Thus, implementing a function which would check for prime would suffice for 30 points as **M<=1000 and N<=1000**

## How To Get 100 Points :-

To get 100 Points , One must implement **The Sieve Of Eratosthenes** in their code.

The Sieve of Eratosthenes is an algorithm for generating a list of all prime numbers up to a given integer **N**. Here the maximum value of **N** is **5000000**.

The algorithm requires one to create an array of size **N+1** , in which each position denotes whether that position (number) is a prime number or not. One must note , that if a number **M is NOT Prime , then it has a factor within <=sqrt(M)** .

It works simply by cutting out all the multiples of Prime Numbers upto a limit and then the remaining numbers left in the Array are Prime.

Let us consider numbers from **1 to 10**.

**1 2 3 4 5 6 7 8 9 10**

We know that 1 isn’t prime so it is safe to cross it off :

**2 3 4 5 6 7 8 9 10**

The smallest number that hasn’t been processed is two, now let’s knock out multiples of twos - by first going to 4,6,8 - all you need is addition!

**2 3 5 7 9**

Now , the smallest unprocessed number is 3. It is now safe to knock off multiples of 3

**2 3 5 7**

**VOILA!** The remaining numbers in the Array are **PRIME!**

The **PseudoCode** for this algorithm is as follows :

func sieve( var N )

var PrimeArray as array of size N+1

initialize PrimeArray to all true

for i from 2 to N

for each j where i divides j, j from i + 1 to N

set PrimeArray( j ) = false

At the end, **PrimeArray(x) will be true if x is a prime number**.

The code can be optimized by running the ‘i’ loop from 2 to <=Math.sqrt(N) using the principle that if a number M is Not Prime , it must have a factor within <=sqrt(M). The ‘j’ loop would then run from i+i to n and the increment value would also be i.

func sieve( var N )

var PrimeArray as array of size N+1

initialize PrimeArray to all true

for i from 2 to sqrt(N)

if PrimeArray(i)==true, j from i + i to N , j+=i

```
set PrimeArray( j ) = false
```

**After computing the Sieve , You simply have to iterate from M to N and add if PrimeArray(i) (i is loop var) is true.**