ライブラリの場合、最初の素数を制限 L まで格納する必要があります。このコレクションには O(1) ルックアップ時間が必要であり (数値が素数かどうかを確認するため)、数値が与えられれば簡単でなければなりません。次の素数を見つけます (L より小さいと仮定します)。
L が固定されている場合、リストを生成するためのエラトステネふるいは問題ありません。現在、パックされたブール配列を使用してリストを保存しています。これには、3 から L (両端を含む) までの奇数のエントリのみが含まれています。これには (L-2)/2 ビットのメモリが必要です。より多くのメモリを使用せずに L を静的に増加できるようにしたいと考えています。
同様のプロパティでメモリ使用量が少ないデータ構造はありますか? または、少なくとも一定のルックアップ時間で？(素数が得られるまで、奇数を列挙できます)
（私がこれを書いた言語はFactorですが、この質問は、組み込みまたは簡単にプログラム可能なパックビット配列を持つ言語でも同じです）
より多くの素数を明示的にチェックして、冗長性を取り除くことができます。
現時点では、明示的に 2 で割り切れるかどうかをチェックし、素数であるかどうかを奇数に対してのみ格納することにより、これを 2 に対してのみ行います。
2 と 3 の余りは 0 から 5 で、そのうち 1 と 5 だけは 2 または 3 で割り切れず、素数になる可能性があるため、1/3 になります。
2、3、および 5 の場合、30 個のうち 8 個の数値が得られます。これは、1 バイトに格納するのに適しています。
これについては、こちらで詳しく説明しています。
パックされたビットマップとホイールに代わるものですが、特定のコンテキストでは同等に効率的ですが、連続する素数間の差を格納します。通常どおり 2 を省略した場合、すべての差は偶数になります。difference/2 を格納すると、バイトサイズの変数を使用して、最大 2^40 領域 (1999066711391 の直前) を取得できます。
オッズのみのパックされたビットマップの 256 MB と比較して、素数 2^32 は 194 MB しか必要としません。デルタ格納された素数の反復は、オッズのみのビットマップとして知られるモジュロ 2 ホイールを含むホイール ストレージよりもはるかに高速です。
1999066711391 以降の範囲では、より大きなセル サイズまたは可変長ストレージが必要です。後者は、510/2 よりも長いギャップの頻度が非常に低いため、非常に単純なスキームが使用されている場合でも非常に効率的です (たとえば、LZ4スタイルの圧縮のように、255 バイト未満のバイトが追加されるまで追加を続けます)。
効率的には、範囲をセクション (ページ) に分割し、B-Tree スタイルで管理するのが最善です。
違いをエントロピー コーディング (ハフマンまたは算術コーディング) すると、永続ストレージの要件が半分以下に削減されます。これは、理論上の最適値に近く、利用可能な最良のパッカーを使用して圧縮されたリストまたはホイールよりも優れています。
データが非圧縮で保存されている場合でも、2 進数またはテキスト数値のファイルよりも 1 桁以上コンパクトになります。B ツリー スタイルのインデックスを使用すると、必要に応じてセクションをメモリにマップし、超高速で反復処理することが簡単にできます。
現時点では、2 を特別なケースとして扱っており、すべての奇数が配列内の要素にマップされている配列を持っています (いくつかの奇数は素数です)。残りの素数が 6n+1 または 6n-1 の形式であることを認識する特殊なケースとして 2 と 3 を扱うことで、これを改善できます (つまり、p > 3、p mod 6 = 1 または5)。これはさらに一般化できます -ウィキペディアを参照してください。すべての素数 p > 5 について、p mod 30 = 1、7、11、13、17、19、23、または 29 です。これを続けて、処理時間を犠牲にして必要なメモリを減らすことができます (ただし、 O(1)、ただ遅い O(1))。
おそらく、素数のみを含むtrieデータ構造が探しているものです。文字をインデックスとして使用する代わりに、整数の数字を使用できます。これの実装はJudy-Arrayです。
ただし、それらは O(1) の要件を満たしていませんが、同様のキーに対して非常にメモリ効率が高く (数値のほとんどの部分がそうであるように)、O(m) (m=key-length) で検索するのが非常に高速です。最大。
事前に生成されたツリーで素数を検索する場合は、それが見つかるまで、または前後の素数の隣にあるノードに到達するまで、ツリーをたどることができます。
メモリが非常に安価であることを考えると、速度の観点から、既存のスキームよりもはるかに優れているとは思いません。
より良い解決策があれば、 L が大きくなるにつれて、極限が
π(L) / (L / ln(L)) は 1 に近づきます。
おそらく、より良い解決策は、スキップ リストのようなデータ構造での適応型パッキング ソリューションです。
ある種のハッシュテーブルはどうですか？
非常に優れたハッシュ関数が必要になります ( のようなもので、 は最低の素数の倍数ではありません。衝突の数を最小限に抑えるために、十分に高い値を選択n mod pしpてください)。qq
どれがメルセンヌまたは他の簡単に表現される素数であるかを把握できれば、その表現を適用可能な数のフラグとともに使用することで、いくつかのビットを節約できる可能性があります。
また、数値を前の数値との差分として保存してみてはいかがでしょうか。その場合、サイズはそれほど速く増加しないはずです (ただし、ルックアップは遅くなります)。上記のアプローチと組み合わせて、メルセンヌ素数と最後のメルセンヌ素数との差を保存できます。