Sieve of Eratosthenes problem: handling really big numbers

Question

I'm solving Sphere's Online Judge Prime Generator using the Sieve of Eratosthenes.

My code works for the test case provided. But.. as the problem clearly states:

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

I know that the method Integer.parseInt() throws an Exception when handling really big numbers and the online judge was indicating that an Exception was being thrown, so I changed every case of parseInt to parseLong in my code.

Well, the thing is running fine on Netbeans 6.5 with small values for m and n.

package sphere;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{

public static void runEratosthenesSieve(long lowerBound, long upperBound) {

      long upperBoundSquareRoot = (long) Math.sqrt(upperBound);

      boolean[] isComposite = new boolean[(int)upperBound + 1];

      for (int m = 2 /*int m = lowerBound*/; m <= upperBoundSquareRoot; m++) {

            if (!isComposite[m]) {

                if (m>=lowerBound) {System.out.println(m);}

                  for (int k = m * m; k <= upperBound; k += m)

                        isComposite[k] = true;

            }

      }

      for (int m = (int)upperBoundSquareRoot; m <= upperBound; m++)

            if (!isComposite[m])

                 if (m>=lowerBound){ System.out.println(m);}

}

public static void main(String args[]) throws java.lang.Exception{

       BufferedReader r = new BufferedReader(new InputStreamReader(System.in));


       String l = r.readLine();

       int testCases = Integer.parseInt(l); 

       for (int i =0; i<testCases; i++){
       String s =r.readLine();

       String []splitted=s.split(" ");


       long lowerBound = Long.parseLong (splitted[0]);
       long upperBound = Long.parseLong(splitted[1]);

       runEratosthenesSieve (lowerBound,upperBound);

       System.out.println("");
       }
}

}

Input+Output:

run:
2
1 10
2
3
3
5
7

3 5
3
5

BUILD SUCCESSFUL (total time: 11 seconds)

But JCreator LE is saying this:

2
1 10
Exception in thread "main" java.lang.NumberFormatException: For input string: ""
    at java.lang.NumberFormatException.forInputString(NumberFormatException.java:48)
    at java.lang.Long.parseLong(Long.java:424)
    at java.lang.Long.parseLong(Long.java:461)
    at sphere.Main.main(Main.java:51)

Process completed.

Here I don't have an integer overflow, but why would jcreator complain?

Considering the borderline testcase, the program implodes on Netbeans too:

run:
2
999900000 1000000000 
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
        at sphere.Main.runEratosthenesSieve(Main.java:13)
        at sphere.Main.main(Main.java:55)
Java Result: 1

How can I deal with those huge-ish integers of the problem statement?

Edit: By suggestion I have changed the boolean array for a BitSet, but I'm still getting an OutOFMemoryError:

package sphere;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.BitSet;

public class Main{

public static void runEratosthenesSieve(long lowerBound, long upperBound) {

      long upperBoundSquareRoot = (long) Math.sqrt(upperBound);

      //boolean[] isComposite = new boolean[(int)upperBound + 1];

      BitSet isComposite = new BitSet((int)upperBound+1);

      for (int m = 2 /*int m = lowerBound*/; m <= upperBoundSquareRoot; m++) {

            if (!isComposite.get(m)) {

                if (m>=lowerBound) {System.out.println(m);}

                  for (int k = m * m; k <= upperBound; k += m)

                        isComposite.set(m);

            }

      }

      for (int m = (int)upperBoundSquareRoot; m <= upperBound; m++)

            if (!isComposite.get(m))

                 if (m>=lowerBound){ System.out.println(m);}

}

public static void main(String args[]) throws java.lang.Exception{

       BufferedReader r = new BufferedReader(new InputStreamReader(System.in));


       String l = r.readLine();

       int testCases = Integer.parseInt(l); 

       for (int i =0; i<testCases; i++){
       String s =r.readLine();

       String []splitted=s.split(" ");


       long lowerBound = Long.parseLong (splitted[0]);
       long upperBound = Long.parseLong(splitted[1]);

       runEratosthenesSieve (lowerBound,upperBound);

       System.out.println("");
       }
}

}

Input-Output:

run:
1
999900000 1000000000
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
        at java.util.BitSet.initWords(BitSet.java:144)
        at java.util.BitSet.<init>(BitSet.java:139)
        at sphere.Main.runEratosthenesSieve(Main.java:16)
        at sphere.Main.main(Main.java:58)
Java Result: 1
BUILD SUCCESSFUL (total time: 14 seconds)

Answer 1

Here's your problem:

boolean[] isComposite = new boolean[(int)upperBound + 1];

This will use a HUGE amount of space since it allocates 4 bytes per boolean in order to allow faster access. Use a java.lang.BitSet to avoid that.

Eventually, your numbers might get too big for long as well and you'll have to use BigInteger. But at that point, the sieve of Eratosthenes will probably not cut it anymore as well.