×

# CDQU1 - Editorial

Author: Animesh Fatehpuria
Testers: Rajat De Sumit Shyamsukha
Editorialist: Animesh Fatehpuria

SIMPLE

# PREREQUISITES:

Sieve Of Eratosthenes

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

# AUTHOR'S SOLUTION:

This question is marked "community wiki".

8831422
accept rate: 9%

19.8k350498541

 0 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-http://ideone.com/Q8TXj1 answered 22 Dec '16, 00:32 5★salman_1 1 accept rate: 0% Got it.... (22 Dec '16, 00:36) salman_15★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,719
×1,173
×301
×199
×12

question asked: 07 Dec '14, 12:55

question was seen: 2,166 times

last updated: 22 Dec '16, 00:36