×

 0 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 2★codegagu 31●9●19●25 accept rate: 0%

 3 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 ...:) answered 05 Jul '13, 09:42 3★dush22 61●4 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×2,556
×418
×300
×69

question asked: 05 Jul '13, 03:06

question was seen: 3,100 times

last updated: 05 Jul '13, 09:42