問題タブ [sieve]

私は乱数の範囲を持っています。範囲は実際にはユーザーによって決定されますが、最大 1000 の整数になります。それらは次の場所に配置されます。

値は次のように挿入されます。

すべての非素数の値を見つけるための別の関数を作成しています。これが私が今持っているものですが、シリーズでプライムとコンポジットの両方を取得するので、それが完全に間違っていることはわかっています.

この方法は通常、0 から 1000 までの一連の数字を持っていたときに機能しましたが、順番が狂って重複している場合は機能していないようです。ベクトルで非素数を見つけるためのより良い方法はありますか? 別のベクトルを作成し、n 個の数値で埋めて、その方法で非素数を見つけたくなるのですが、それは非効率的でしょうか?

範囲は 0 ～ 1000 であるため、0 ～ n を並べ替えてベクトルを作成し、ふるいを使用して素数を見つける方が簡単かどうか疑問に思っていますが、これは近づいていますか?

n番目の素数の近似値を返す関数はありますか? これはおおよその逆素数カウント関数のようなものになると思います。たとえば、この関数に 25 を指定すると、約 100 の数値が返されます。または、この関数に 1000 を指定すると、約 8000 の数値が返されます。返される数値が素数かどうかは気にしませんが、それは高速です（したがって、 n番目を返すために最初のn個の素数を生成しません。）

ふるい（ EratosthenesまたはAtkin ）を使用して最初のn個の素数を生成できるように、これが欲しいです。したがって、n番目の近似は、理想的には実際のn番目の素数の値を過小評価することはありません。

(更新: n番目の素数の上限を見つける良い方法については、私の回答を参照してください。)

オイラーのふるいと呼ばれるエラトステネスのふるいの一種の改良版に出くわしたとき、私はさまざまなふるいアルゴリズムについて読んでいました。ウィキペディアによると、Haskell には少し異なるバージョンのアイデア (Turner's Sieve と呼ばれる) の実装があります。

今、私は与えられたコード スニペットが正確に何をするのかを理解しようとしています。私はそれを理解していると思いますが、今はコードを F# に変換したかったのですが、どこから始めればよいのか本当にわかりません。私の主な懸念は、2 つのシーケンスを「減算」する機能がないように見えることです。

コードは次のとおりです。

これを F# でどのように実装しますか? それは可能ですか？

私が思うコードで最もよく説明されているのは、これは単なる例です。

醜いです。基本的に私はコレクションを持っており、それをある種のふるいに通して、特定の条件を満たすオブジェクトのみの処理を続行したいと思います。私の推測では、これにはブール値を返す一連のメソッドよりも優れたパターンがあります。

空き時間にプロジェクト Euler をプレイしていて、リファクタリングが必要なところまで来ました。Miller-Rabin といくつかのふるいを実装しました。ふるいは、数百万未満のように小さい数の方が実際には高速であると以前に聞いたことがあります。誰もこれに関する情報を持っていますか？Google はあまり役に立ちませんでした。

彼らは正確に何をしますか？@ (パターン マッチの開始時に名前を割り当てる) の 1 つの可能な使用法を知っていますが、~ で何も見つけることができませんでした。

http://www.haskell.org/haskellwiki/Prime_numbersから取得した次のコード スニペットでそれらを見つけましたが、この記事では、Haskell 構文に精通していることを前提としており、難解な演算子については説明していません ( ' sieveの宣言の開始について混乱しています):

ここで使用されている構文に関する説明 (または説明へのリンク) をいただければ幸いです。

私はエラトステネスのふるいを実装しています。これについての説明はhttp://en.wikipedia.org/wiki/Sieve_of_Eratosthenesを参照してください。ただし、素数1からNではなく、M素数を生成するように適合させたいと思います。これを行う方法は、すべてのM素数がこの範囲に含まれるように十分な大きさのNを作成することです。素数の成長をモデル化するための優れたヒューリスティックを持っている人はいますか？コードスニペットを投稿したい場合は、これをJavaとC++で実装しています。

Project Eulerに関する質問を解きながら、Eratosthenes のふるいを読みました。私はあなたが私が話している質問を知っていると確信しています。これが問題です。私のコードは、100 万未満のすべての素数を正しく表示することができます。しかし、200 万に対して同じ実装を試みると、セグメンテーション違反が発生します...エラーが発生する理由については一定の考えがありますが、それを修正する方法がわかりません... 100 万未満の素数のコードは次のとおりです。 .

ウィキペディアの車輪の因数分解の手順に従っていると、2-3-5-7 の車輪を作ろうとすると、素数 331 が合成数として扱われるという問題に遭遇したようです。

2-3-5-7 ホイールの場合、2*3*5*7=210。そこで、210 スロットのサークルをセットアップし、手順 1 ～ 7 を問題なく実行しました。次に、ステップ 8 に進み、素数のすべての倍数のスポークを削除します。最終的には、素数である 11 の倍数である 121 に根ざしたスポークを削除します。121 を根とするスポークの場合、121 + 210 = 331 です。残念ながら、331 は素数です。

ウィキペディアの手順は間違っていますか？

それとも手順を誤解していたので、2、3、5、および 7 の倍数であるスポークのみを削除し、210 未満の他の素数は削除すべきではなかったのでしょうか?

上記のコードは、友人が素数を取得するために作成したものです。ある種のふるい分けを使用しているようですが、正確にどのように機能するかはわかりません。以下のコードは、それほど素晴らしいバージョンではありません。私は自分のループに使用sqrtしますが、彼が何か他のことをしているのを見た (おそらく関連するふるい) ので、気にしませんでした。

私の質問は、彼は正確に何をしているのですか?