11

600851475143 より前のすべての素数を取得しようとしていました。これにはエラトステネスのふるいを使用していました。これには、その巨大なサイズのブール配列を作成する必要があります。悪い考えです。メモリが不足する可能性があります。その他の方法で。値 0 と 1 を持つ各インデックスを使用して、true または false を表す文字列を使用してみました。しかし、indexOf メソッドも int を返します。

次に、問題に 2 次元配列を使用しています。このような巨大な配列を保存する他の良い方法はありますか?

4

5 に答える 5

7

600851475143 ブール値のメモリ要件は、せいぜい 70Gb です。これは実現不可能です。Stephan の提案に従って圧縮を使用するか、素数を計算するための別のアルゴリズムを見つける必要があります。

于 2013-04-15T12:17:44.247 に答える
6

同様の問題があり、ビットセットを使用しました（基本的には、目的のオフセットに1または0を順番に設定します）。EWAHCompressedBitmapを使用することをお勧めします。ビットセットも圧縮します

編集

アランが言ったように、BitSet は 70GB のメモリを占有しますが、別のこともできます: 複数の BitSet (絶対位置を計算できるように連続したもの) を持ち、その瞬間に必要な BitSet だけをメモリにロードします。この場合、使用するメモリを制御できます。

于 2013-04-15T12:15:56.887 に答える
2

それが素数であったかどうか、またはそのような大量ではない場合、各数値を覚えておくのは実際には実用的ではありません（ふるいは、一般的に大きな数値に対して非常に遅いアプローチです）。

このリンクから、X より小さいと予想される素数がいくつあるかがわかります。6,000 億の範囲では、その範囲内に約 200 億の素数が存在すると予想できます。それらを long[] として保存するには、約 160GB のメモリが必要になります...これは、偶数を除外すると (2 が唯一の素数である)、数値ごとに 1 ビットを保存するために推奨される 70GB よりも特に多くなります。

デスクトップ コンピューターの場合、35 GB のメモリは少し多いかもしれませんが、優れたワークステーションにはそれだけの量の RAM を搭載できます。ビットシフト/マスキングを使用して2次元配列を試してみます。

私はまだあなたのふるいコードがかなりの時間 (数日から数年)実行されることを期待しています。ふるいよりも高度なプライム検出方法を調査することをお勧めします。

于 2013-04-15T14:09:38.657 に答える
0

BitSetを使用します。次に、任意のインデックス要素にビットを設定できます。したがって、 600851475143 は2^39内部で 39 ビットしか使用していません (実際には long を使用するため、64 ビットを占有します)。

2^63実際、ほとんどの目的で大規模なまでに移動できます

于 2013-04-15T12:15:10.000 に答える