私はエラトステネスのふるいを使ってスフィアのオンラインジャッジプライムジェネレーターを解いています。
私のコードは、提供されたテストケースで機能します。しかし..問題が明確に述べているように：
入力は、1行のテストケースの数tから始まります（t <= 10）。次のt行のそれぞれに、スペースで区切られた2つの数値mとn（ 1 <= m <= n <= 1000000000、nm <= 100000）があります。
非常に大きな数を処理するときにメソッドInteger.parseInt()が例外をスローし、オンラインジャッジが例外がスローされていることを示していたので、コード内のすべてのケースparseIntをに変更しました。parseLong
さて、mとnの値が小さいNetbeans6.5では問題なく動作しています。
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("");
}
}
}
入力+出力：
run:
2
1 10
2
3
3
5
7
3 5
3
5
BUILD SUCCESSFUL (total time: 11 seconds)
しかし、JCreatorLEはこれを言っています：
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.
ここでは整数のオーバーフローはありませんが、なぜjcreatorが文句を言うのでしょうか。
境界テストケースを考慮すると、プログラムはNetbeansにも影響を及ぼします。
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
問題ステートメントのこれらの巨大な整数をどのように処理できますか？
編集：提案により、BitSetのブール配列を変更しましたが、まだ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("");
}
}
}
入出力：
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)