PROBLEM LINKS:Author: Animesh Fatehpuria DIFFICULTY:SIMPLE PREREQUISITES:PROBLEM:Given Two Numbers M and N , Find the Sum of Prime Numbers between M and N (inclusive). 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. Let us consider numbers from 1 to 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 ) 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 ) 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".
asked 07 Dec '14, 12:55

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 linkhttp://ideone.com/Q8TXj1 answered 22 Dec '16, 00:32
