私はエラトステネスのふるいを実装しています。これについての説明はhttp://en.wikipedia.org/wiki/Sieve_of_Eratosthenesを参照してください。ただし、素数1からNではなく、M素数を生成するように適合させたいと思います。これを行う方法は、すべてのM素数がこの範囲に含まれるように十分な大きさのNを作成することです。素数の成長をモデル化するための優れたヒューリスティックを持っている人はいますか？コードスニペットを投稿したい場合は、これをJavaとC++で実装しています。
5 に答える
4
M 個の素数を生成するには、約 M log M まで上げる必要があります。素数定理に関するウィキペディアの記事で、n 番目の素数の近似を参照してください。安全のために、過大評価することをお勧めします。たとえば、N = M (log M + 1) とします。
追加するために編集: David Hammen が指摘するように、この過大評価は常に十分であるとは限りません。ウィキペディアの記事では、M >= 6 の安全な上限として M (log M + log log M) を示しています。
于 2011-09-26T18:15:45.187 に答える
3
この n 番目の素数の近似は、ウィキペディアから取得されます。m*log(m)+m*log(log(m))したがって、 ;の配列を割り当てるだけで済みます。の配列でm*log(m)は不十分です。
于 2011-09-26T18:51:23.493 に答える
1
別の代替手段は、セグメント化されたふるいです。数を百万にふるいにかけます。それから2番目の100万。それから3番目。等々。足りなくなったらやめる。
次のセグメントのためにふるいをリセットするのは難しくありません。詳細については、私のブログを参照してください。
于 2011-09-26T19:49:08.663 に答える
0
ふるいを動的に成長させてみませんか? さらに素数が必要な場合はいつでも、seive メモリを再割り当てし、以前に見つけた素数を使用して、新しいスペースのすぐ上で sieve アルゴリズムを実行します。
于 2011-09-26T18:23:49.767 に答える
0
遅延評価が頭に浮かびます (Haskell や他の関数型言語がそれを行います)。あなたは命令的な言語で書いていますが、私が思うにその概念を適用することができます.
残りの基数を候補セットから削除する操作を考えてみましょう。実際のアルゴリズムに実際に触れずに (さらに重要なことに、作成する数を推測せずに)、この操作を怠惰な方法で実行します (命令型言語を使用しているため、実装する必要があります) 。残りの最小数を取る。
于 2011-09-26T19:11:32.617 に答える