エラトステネスの篩やアトキンなど、多くの素数発生器があることを私は知っています。ただし、小さいものから順番に数字を生成します。小さい方から始めずに間隔内の素数を取得するには、どの方法を使用できますか?
オプションは、乱数ジェネレーターを使用し、達成したいことに応じて、決定論的または確率論的な素数テストで出力をテストすることです。とにかく、テストは遅くて複雑です。
素数を非連続的に生成するための迅速かつ簡単な方法はありますか? 疑似素数ジェネレーターも問題ありません。
よろしく
質問をより明確に書き直します。
特定の間隔で素数を生成するにはどうすればよいですか? - (エラトステネスのふるいのように) 小さいものから大きいものへ順番に移動することも、ランダムなシーケンスで遅い確率的素数性テストを使用することもありませんか?
長時間実行すると一定間隔ですべての素数が得られるような方法で数値を生成する FAST および EASY アルゴリズムまたは関数はありますか? (それがいくつかのコンポジットを生成するかどうかは気にしません)。
間隔が大きすぎず、間隔の下端が高すぎない場合は、セグメント化されたエラトステネスのふるいを使用できます。「大きすぎる」と「高すぎる」の定義は、あなたの願望と忍耐力に依存しますが、約 10 の 15 乗よりも大きいものは成功する可能性が低いです。それ以外の場合は、目的の間隔でランダムな奇数を選択し、素数をテストして、素数である場合はそれを保持するか、素数が見つかるまで次に大きな奇数を試すことができます。次の奇数をテストするだけでなく、素数ホイールを使用して素数候補を生成することで、必要に応じて速度を上げることができます。第三の選択肢はありません。
合成数ならあまり気にしないとおっしゃいましたね。その場合、ランダムな奇数を生成し、基数 2 への強い疑似素数性のみをテストし、他の基数がないことをテストし、テストで素数であると判断された場合はそれを保持するか、テストで素数であると判断された場合は次の奇数で再試行することができます。複合。これは完全な素数性検定ではありませんが、Miller-Rabin 検定で乱数ベースの 25 検定を実行するよりも高速であり、Lucas 疑似素数検定よりも高速であり、目的には十分である可能性があります。
これらすべての説明は、Stack Overflow で検索するか、私のブログを参照することで見つけることができます。さらに具体的な質問がある場合は、ここで質問することもできます。