views:

558

answers:

3

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

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.

AlbertoPL
It's BigDecimal, not BigDouble
Michael Borgwardt
Haha woops, it's late.
AlbertoPL
+5  A: 

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.

Michael Borgwardt
hmm...how can I sieve the bigger numbers after 10^6?
omgzor
http://en.wikipedia.org/wiki/Sieve_of_Atkin
Michael Borgwardt
I'm still getting the OutOfMemoryError when using BitSet.
omgzor
Well, it's still over 100MB, so you'll have to give the JVM enough memory using the -Xmx option. Alternatively use the other method I linked to; it has a lower memory use.
Michael Borgwardt
A: 

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.

Jack