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.