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.