N が大きい場合、 1 < k < N となるようにすべての phi(k) を反復処理する必要があります。

• 時間複雑度はO(N logN)
• memory-complexity はサブでなければなりませんO(N)(N の値が約 10 ¹²になるため)

出来ますか？もしそうなら、どのように？

ライブラリの場合、最初の素数を制限 L まで格納する必要があります。このコレクションには O(1) ルックアップ時間が必要であり (数値が素数かどうかを確認するため)、数値が与えられれば簡単でなければなりません。次の素数を見つけます (L より小さいと仮定します)。

L が固定されている場合、リストを生成するためのエラトステネふるいは問題ありません。現在、パックされたブール配列を使用してリストを保存しています。これには、3 から L (両端を含む) までの奇数のエントリのみが含まれています。これには (L-2)/2 ビットのメモリが必要です。より多くのメモリを使用せずに L を静的に増加できるようにしたいと考えています。

同様のプロパティでメモリ使用量が少ないデータ構造はありますか? または、少なくとも一定のルックアップ時間で？(素数が得られるまで、奇数を列挙できます)

（私がこれを書いた言語はFactorですが、この質問は、組み込みまたは簡単にプログラム可能なパックビット配列を持つ言語でも同じです）

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

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

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

可分性をチェックするコードを熱心にプラグインしています (はい、素数を生成するためです)。条件が 1 回満たされた場合に for... ループを停止する方法を知りたいです。次のようなコード:

$testarray1 ～ 100 の整数も同様であり、配列$deleteは に対してフィルタリングされ$testarrayます。$deleteただし、現在、12 のような数は、2、3、4、および 6 で割り切れるため、複数回追加されています。条件が 1 回一致したときに先にスキップして、コンピューターの時間を節約するにはどうすればよいですか?

私が作成した関数で Seq.cache を使用しようとしています。これは、数値 1 を除く数値 N までの素数のシーケンスを返します。キャッシュされたシーケンスをスコープ内に保持する方法を理解するのに問題がありますが、それでも使用します私の定義では。

Seq.cache を使用してこれを高速化する方法についてのアイデアはありますか? 現在、スコープから外れ続けており、パフォーマンスが低下しているだけです。

2つの数の間のすべての素数を印刷したい。これは私のコードです：

1 10で実行すると、出力は次のようになります。

なぜ7時に止まらないのですか？

昨日、空き時間に F# を調べ始めました。100 までのすべての素数を出力するという標準的な問題から始めようと思いました。

問題は、C/C# の観点からこれにアプローチしたように感じ、真の関数型言語の側面を受け入れていないことです。

他の人が何を思い付くことができるのか、そして誰かがヒント/ポインター/提案​​を持っているかどうか疑問に思っていました. F# のコンテンツは現在 Web で入手するのが難しく、私が最後に触れた関数型言語は大学時代の 5 年前にHOPEでした。

免責事項: 私はオイラー問題 9 に取り組んでいます。

1 から 2 000 000 までのすべての素数を、いくつかのかなり大きな数を合計しています。

これらの素数を合計すると、永遠にかかります。関数「sum」に組み込まれているhaskellを使用しています。

次のように:

他に高速なオプションはありますか?

--私のプライム ジェネレーターは、コード内の低速リンクでした。