素数を探索するプログラムを作ってみました。 やり方は、古典的な「エラトステネスの篩」になりました。

もっと効率的とも言われる「ミラー–ラビン素数判定法」も試したのですが、問題が大でした。 確かに、ある一つの数値に対する予測をするだけなら短時間でできる場合もあるのですが、 大きな数の領域、例えば C# の Long（64 ビット）の最大に近い領域では、素数の密度は疎らで、50個に１個くらいしかなく、 そういう状況下で素数を探すためには結局「エラトステネスの篩」で一気に調べる方が早いと言えました。 「ミラー–ラビン素数判定法」は所詮、予想、仮説、というレベルのものでしかない点も問題でした。 ただし、開発の過程で動作の検証をするために「ミラー–ラビン素数判定法」のお世話にもなりました。 十億程度までは両者の一致も確認しています（プログラムでコメントアウトした部分）。

「エラトステネスの篩」では、最も小さい素数から順に、どれが素数かのデータを残さなければなりません。 しかし、例えば M という数とその直下の少しの領域を調べるためには、√M まで連続して保存されたデータがあれば足ります。 また、そこまでの保存データを作るためには、さらにそのルートまでのデータを因数候補として検討すれば足ります。 このように、目標を決めたら節約できるところは節約するというのが、探索を効率化するコツということになります。 手元の PC で、1e18（Long の最大桁）前後の探索では、15 秒という結果を得ています。

大きな素数は、疑似乱数生成のための定数として使うことを考えています。 具体的な使い方のポリシーを既に持っているわけではありません。 それを開発し、検証するための手段です。