You are not logged in. Please login at www.codechef.com to post your questions!

×

CDQU1 - Editorial

PROBLEM LINKS:

Practice
Contest

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

DIFFICULTY:

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:

Author's solution .

This question is marked "community wiki".

asked 07 Dec '14, 12:55

animesh_f's gravatar image

6★animesh_f ♦
8831422
accept rate: 9%

edited 08 Dec '14, 19:06

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 22 Dec '16, 00:32

salman_1's gravatar image

5★salman_1
1
accept rate: 0%

Got it....

(22 Dec '16, 00:36) salman_15★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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