 This post was flagged by the community and is temporarily hidden.

Well…You are almost on the right track.However some optimizations are needed.

1. This problem requires the use of modified Sieve of Eratosthenes. (I’l come back to it in a moment)

2. Secondly, you need to observe that no matter what values you get in the test cases , `1 <= m <= n <= 1000000000` is always true. So instead of finding out primes for each individual test case, you do, what is called, preprocessing i.e. Before you even start processing the test cases, you evaluate all the primes.(In this case, however, complete preprocessing is not possible, owing to the large size of the input.)

3. Before proceeding further, I’ll like to mention some optimizations in the general implementation of the Sieve of Eratosthenes.

If you have to find all prime numbers less than ‘a’, then you should proceed somewhat as follows.

‘boolean flag[a]//Just to check if a number at index ‘i’ is prime or not
Set flag[1:a]=true
int Prime[Some_reasonable_limiting_value]//To Accomodate All Primes
i=2
for i less than square_root(a):
if (flag[i]):
Push_To_Prime_Array(i) and set all multiples of i to false’
//Now since the loop of i executed only upto square_root(a), we proceed further from
// i=Square_Root(a) upto a and push all elements having flag[i]=true into the Prime array

So ultimately what you’ll have in the ’ Prime ’ array is a list of Primes less than ‘a’

Now, Coming back to the problem… Creating an array for 10^9 elements requires a lot of memory which might, or rather would definitely lead to Runtime Exception.

So, what we do is,

i) Compute all primes upto Square_root(10^9)

ii) For any value of (m,n) encountered, we simply re-run the Sieve of Eratosthenes in that range, using the already precomputed Prime numbers we have.

I’ll leave this second part of the problem as an exercise for you. If you understand the principle behind this method, you’ll definitely crack the remaining problem

Happy Coding … 3 Likes