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. asked 05 Jul '13, 03:06

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 , 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.
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 rerun 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 ...:) answered 05 Jul '13, 09:42
