問題タブ [sieve-of-eratosthenes]

Python でエラトステネスのふるいを実装しようとしていますが、たとえば779695003923747564589111193840021の平方根までのすべての素数を見つけようとすると、range() の結果に項目が多すぎるというエラーが表示されます。私の質問は、この問題を回避するにはどうすればよいかということです。リストを while ループでインスタンス化すると、(ページファイルの使用を開始する前に) メモリを使いすぎているというエラーが表示されます。2 つを以下に示します。

range() の使用

while の使用:

ウィキペディアから：

アルゴリズムの複雑さは O(n(logn)(loglogn))ビット演算です。

どうやってそこにたどり着きますか？

複雑さにこのloglogn用語が含まれているということは、sqrt(n)どこかにあることを私に教えてくれます。

最初の100個の数値（n = 100）でふるいを実行していると仮定します。数値を複合としてマークするのに一定の時間がかかると仮定すると（配列の実装）、使用する回数は次のmark_composite()ようになります。

そして、次の素数を見つけるために（たとえば、7の倍数であるすべての数を取り消した後にジャンプするために5）、操作の数はになりますO(n)。

したがって、複雑さはになりますO(n^3)。同意しますか？

エラトステネスの篩と Python 3.1を使用して素数ジェネレーターを作成しました。このコードは、ideone.comで 0.32 秒で正しく適切に実行され、最大 1,000,000 の素数を生成します。

問題は、1,000,000,000 までの数値を生成しようとすると、メモリが不足することです。

ご想像のとおり、10 億のブール値 ( Python ではそれぞれ1 バイト4 または 8 バイト (コメントを参照)) を割り当てることは実際には不可能なので、bitstringを調べました。各フラグに 1 ビットを使用すると、メモリ効率が大幅に向上すると考えました。ただし、プログラムのパフォーマンスは大幅に低下しました。素数が 1,000,000 までの場合、実行時間は 24 秒です。これはおそらくビット文字列の内部実装によるものです。

上記のコード スニペットのように、3 行をコメントまたはコメント解除して、BitString を使用するように変更した内容を確認できます。

私の質問は、ビット文字列の有無にかかわらず、プログラムを高速化する方法はありますか?

編集: 投稿する前にコードを自分でテストしてください。当然、既存のコードよりも実行速度が遅い回答は受け入れられません。

もう一度編集します。

私のマシンのベンチマークのリストをまとめました。

私はClojureでエラトステネスの篩のこの実装を持っています:

それより大きいn(20000 など) 場合は、スタック オーバーフローで終了します。ここでテールコールの除去が機能しないのはなぜですか? 修正方法は？

Clojure での Sieve of Erathosthene の実装を次に示します (ストリームに関する SICP のレッスンに基づく)。

さて、最初の 100 個の素数を取れば問題ありません。

しかし、最初の 1000 個の素数を取ろうとすると、スタック オーバーフローのためにプログラムが中断します。関数ふるいを何らかの方法で変更して末尾再帰になり、それでもアルゴリズムの「ストリームネス」を維持することが可能かどうか疑問に思っていますか?

助けて？

まず第一に、私はこのフォーラムで多くのことをチェックしましたが、十分に速いものを見つけられませんでした。指定された範囲の素数を返す関数を作成しようとしています。たとえば、エラトステネスの篩を使用してこの関数を (C# で) 実行しました。Atkin のふるいも試しましたが、Eratosthenes の方が高速に実行されます (私の実装では):

私が見つけたコードとアルゴリズムよりも約 2 倍高速に実行されます...素数を見つけるためのより高速な方法があるはずです。

私はHaskellでいくつかの古典的な問題を解決して機能スキルを開発していますが、この「プログラミング実践」サイトで提案されている最適化を実装するのに問題があります。

この問題には3つの解決策があり、3番目の解決策は2番目の解決策に比べて遅すぎます。誰かが私のコードの改善を提案できますか？

私の実装は次のとおりです。

SPOJの問題PRIME1を解決するために、エラトステネスのふるいを実装しました。出力は問題ありませんが、私の提出は制限時間を超えています。どうすれば実行時間を短縮できますか？

明確にするために、これは宿題の問題ではありません:)

私が構築している数学アプリケーションの素数を見つけたかったのですが、Sieve of Eratosthenesアプローチに出会いました。

私はPythonでそれの実装を書きました。しかし、それはひどく遅いです。たとえば、200 万未満の素数をすべて見つけたいとします。20分以上かかります。（私はこの時点でそれを止めました）。どうすればこれをスピードアップできますか?

更新: 私はこのコードのプロファイリングを行ってしまい、リストから要素を削除するのにかなりの時間が費やされていることがわかりました。要素を見つけて削除し、リストを再調整するためにリスト全体（最悪の場合）をトラバースする必要があることを考えると、非常に理解できます（おそらくいくつかのコピーが続きますか？）。とにかく、辞書用のリストを取り出しました。私の新しい実装 -

Java で SoE アルゴを簡単に実装しました (最後にコードを示します)。デュアル コア AMD プロセッサでの出力は次のとおりです。

• 「肉」セクションは、予想どおり最大の時間を消費します。

• 私が観察したことの 1 つは、 usingMath.pow(variable, 2)は よりも遅いということでした(variable * variable)。関数のジャンプ以外にも、他にもオーバーヘッドがあるのではないかと思います。

• Math.pow(x, 2) には 2、3 などの累乗の最適化がありますか? Java のネイティブのアルゴリズムよりもはるかに高速な乗算アルゴリズムを備えたユーザー提供の Java ライブラリがいくつかあるため、質問します。

ここに私の質問があります：

• 肉のセクションにどのような算術最適化を提案できますか? モジュラス演算子を完全に回避する方法はありますか?

• start == end の場合、関数は機能しません。sieve(4, 4) を実行すると、返される配列の長さは 1: [4] になります。私は何を間違っていますか？[] (基本的に新しい int(0)) を返す必要があります。

• あなたが知っている高速な数/数学関連のJavaライブラリは何ですか?

読んでくれてありがとう。最後に、私が書いたコードは次のとおりです: GangOfFour/TopCoder の品質ではありませんが、あまりにも哀れではありません (願っています!、SO でのコードの書式設定は一種の....奇妙なものですか?):

すべてのフィードバックに感謝します。これは以下の修正版です（誰かが再びそれを壊すまで:)