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.

Answer 2

You're using a lot of space to store your booleans. You might try to squeeze every boolean into one bit. And think about it, do you realy need a boolean for every number between lowerbound and upperbound? The even numbers for instance are never prime (except for 2), nor are all multiples of 3 (except for 3) etc. This page might give you some good ideas.

Answer 3

There was a small bug in your BitSet implementation. The line:

                    isComposite.set(m);

should actually be:

                    isComposite.set(k);

With that line fixed, the code ran without errors on the test case 999900000 to 1000000000, spitting out 4,832 primes beginning with 999900017 and ending with 999999937. The BitSet used 125 Mbytes of memory, and the method took 17 seconds to run on my 2.2 GHz laptop.

Answer 4

Ae you using the BigInteger class? Because if no, I highly recommend it here. It will deal with the big numbers you are describing. If that is not good enough, then you need to allocate more memory for the JVM to use by doing -Xmx as a command line parameter. There's an example here:

http://www.coderanch.com/t/384456/Java-General-intermediate/java/Increase-JVM-heap-size-eclipse

There is a BigDecimal as well, if you need decimal numbers to be large as well.

Answer 5

I had faced similar issues due the limitations on Java Heap Size. Instead of using high memory Integer, shifting to boolean solved the problem. Find the attached code:

public ArrayList<Integer> sieve(int A) {
    boolean prime [] = new boolean[A + 1];
    Arrays.fill(prime, true);
    prime[0] = prime[1] = false;

    for (int i = 2; i <= A; i++) {
        if (!prime[i])
            continue;

        for (long j = 1L * i * i; j <= (long) A; j += i)
            prime[(int) j] = false;
    }

    ArrayList<Integer> res = new ArrayList<>();

    for (int i = 0; i <= A; i++) {
        if (prime[i])
            res.add(i);
    }

    return res;
}