I have used the Sieve of Eratosthenes to sole this problem but i don’t know how to handle the large numbers(1*10^9).It works fine for lower values but for larger ones, such as:
1
99990011 1000000000
I get this exception:
Exception in thread “main” java.lang.OutOfMemoryError: Java heap space
at roughwork.main(roughwork.java:19)
What are the necessary corrections that has to be made in my code?
Here is my code: http://www.codechef.com/viewsolution/2313065
Thank you.
Well…You are almost on the right track.However some optimizations are needed.
This problem requires the use of modified Sieve of Eratosthenes. (I’l come back to it in a moment)
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.)
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 …