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)