CDQU1 - Editorial




Author: Animesh Fatehpuria

Testers: Rajat De Sumit Shyamsukha
Editorialist: Animesh Fatehpuria




Sieve Of Eratosthenes


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

Given M<=5000000 and N<=5000000


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.


Author’s solution .

I have done exactly in the same way in C++ but I am still getting TLE in 2nd test case.Can any one tell me what is the problem with my code.Here is the link-

Got it…