Sieve of Eratosthenes - HeapMemoryOutOfSpace

Question

So I wrote a code to implement sieve of eratosthenes and It works well for small inputs!! As soon as I take n upto the vicinity of 1000000000 it shows and error, HeapMemoryOutOfSpace. I am at a block here and cannot figure out how to get it to work for such large values. Is there some kind of optimization that can be done for this ?? This is for an online judge so the max value of n is the one that I have already mentioned. This is not for a competition and is for my own practice only. Any kind of help will be appreciated!!

import java.io.*;
class PrimeGenerator
{
public static void main(String args[])
{
    try
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());

        while(t--!=0)
        {
            String k[] = br.readLine().split(" ");

            int m = Integer.parseInt(k[0]);
            int n = Integer.parseInt(k[1]);

            long arr[] = new long[n+2];

            for(long a=2;a<=n;a++)
            {
                arr[(int)a] = 1;
            }

            for(long a=2;a*a<=n;a++)
            {
                if(arr[(int)a]==1)
                {
                    for(long b=a;b*a<=n;b++)
                    {
                        arr[(int)(a*b)]=0;
                    }
                }
            }

            for(int a=2;a<=n;a++)
            {
                if(arr[a]==1&&arr[a]>=m)
                {
                    System.out.println(a);
                }
            }
            System.out.println();
        }
    }
    catch(Throwable e)
    {
        e.printStackTrace();
    }

}
}

Answer 1

Opetion has already pointed out the several structural problems with your code; some bits of the program do not make any sense at all (like if (arr[a] == 1 && arr[a] >= m)). Not to mention that the code does not implement the Sieve of Eratosthenes, even though it uses similar logic. Eratosthenes strikes out multiples of a prime p by starting at index p*p and then incrementing by p (i.e. striding additively).

Two observations, assuming that this is something like the SPOJ PRIME1 problem where you have to print the primes between M and N:

(1) You are using one 64-bit integer (Java long) to represent each candidate number instead of a single bit. Further space and time savings are possible by excluding all even numbers from the array, pulling the number 2 out of thin air if necessary. A bit-packed, odds-only representation needs only 1/128th of the space you are using now. The hard work has already been done for you in java.util.BitSet.

(2) For sieving the numbers in the range [M, N] it is not necessary to sieve all numbers between 2 (or 3) and N. In fact, tasks like SPOJ are designed to make you time out if you try that, even though it is doable with nice clean high-performance code. For sieving the range [M, N] you only need all potential prime factors up to sqrt(N) - which are only a few thousand - and an array of size (N-M+1) for the actual sieving. Or (N-M)/2, for an odds-only sieve. That only takes a few milliseconds and not much space at all.

For SPOJ you don't even have to use packed bit representations or odds-only sieving. Just concentrating on windowed sieving alone lets you beat the task handily, with space and time to spare.

Answer 2

You need to tune the JVM and increase the heap size.

If you are running the program in console you can increase the size like so:

java -Xmx6g myprogram

This command increases the heap size to 6 gigabytes, increase this whatever your system can handle.

If you are running eclipse or another IDE you will have to lookup how to tune the JVM for running that program in your IDE, but it will probably resemble the command above.

Answer 3

For primes up to 1000000000 you don't need to increase your heap size in a proper implementation.
Some problems with your implementation of Sieve of Eratosthenes:

• Why use longs when you are just storing 0 ands 1?
  There is a primitive type that uses only 0's ands 1's ( false and true ) called boolean.

• Why recalculate every single prime again?
  You can calculate every single prime once ( up to a maximum of the integer max number) and then just check the list or print them all.