You are not logged in. Please login at www.codechef.com to post your questions!

×

PRIME GENERATOR(PRIME1) NZEC. please help

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

codegagu's gravatar image

2★codegagu
3191925
accept rate: 0%

edited 05 Jul '13, 03:10


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 ...:)

link

answered 05 Jul '13, 09:42

dush22's gravatar image

3★dush22
614
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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