エラトステネスのふるい問題：本当に大きな数字を処理します

StackOverflow https://stackoverflow.com/questions/1077907

質問

私はSphereのオンライン裁判官を解決しています プライムジェネレーター エラトステネスのふるいを使用します。

私のコードは、提供されたテストケースで機能します。しかし..問題が明確に述べているように：

入力は、単一行のテストケースの数から始まります（t <= 10）。次のt行のそれぞれに、2つの数値mとnがあります（1 <= m <= n <= 1000000000、nm <= 100000） スペースで区切られています。

私はその方法を知っています Integer.parseInt() 本当に大きな数字を処理するときに例外をスローし、オンライン裁判官が例外がスローされていることを示していたので、私はのすべてのケースを変更しました parseInt に parseLong 私のコードで。

さて、MとNの値が小さいNetBeans 6.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)

しかし、JCreator Leはこれを言っています：

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は不平を言うのでしょうか？

ボーダーラインのテストケースを考慮すると、プログラムはネットビーンにも内破します。

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

問題声明のそれらの巨大な整数にどのように対処できますか？

編集： 提案により、私はビットセットのブールアレイを変更しましたが、まだ取得しています 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)
役に立ちましたか？

解決

これがあなたの問題です：

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

これは、より速いアクセスを可能にするためにブール波あたり4バイトを割り当てるため、膨大な量のスペースを使用します。使う java.lang.bitset それを避けるために。

最終的には、あなたの数も大きくなりすぎて、Bigintegerを使用する必要があります。しかし、その時点で、エラトステネスのふるいはおそらくもうそれをカットしないでしょう。

他のヒント

ブリアンを保管するために多くのスペースを使用しています。すべてのブール値を1ビットに絞り込もうとするかもしれません。そして、それについて考えてください、あなたは本当に低い境界と上限の間のすべての数に対してブール値が必要ですか？たとえば、偶数はプライムではなく（2を除く）、すべての倍数（3を除く）などでもありません。 このページ あなたにいくつかの良いアイデアを与えるかもしれません。

ビットセットの実装には小さなバグがありました。この線：

                    isComposite.set(m);

実際にあるべきです：

                    isComposite.set(k);

その行が固定された状態で、コードはテストケース999900000から1000000000にエラーなしで実行され、999900017で始まり99999937で終了する4,832のプライムを吐き出しました。ラップトップ。

bigintegerクラスを使用していますか？いいえの場合は、ここで強くお勧めします。それはあなたが説明している大きな数字を扱います。それだけでは十分でない場合は、コマンドラインパラメーターとして-XMXを実行することにより、JVMが使用するために、より多くのメモリを割り当てる必要があります。ここに例があります：

http://www.coderanch.com/t/384456/java-general-intermediate/java/increase-jvm-heap-size-eclipse

小理数も大きくする必要がある場合は、大きなdecimalもあります。

Java Heapサイズの制限により、同様の問題に直面していました。 High Memory Integerを使用する代わりに、Booleanにシフトすると問題が解決しました。添付のコードを見つけます：

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;
}
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top