問題タブ [sieve-of-eratosthenes]

Erlangを勉強中です。演習として、素数を生成するエラトステネスのふるいアルゴリズムを取り上げました。これが私のコードです：

このコードは実際に機能します:)。問題は、それが可能な限り最良の実装ではないと私が感じていることです。

私の質問は、「エラトステネスのふるい」を実装する「エルラン語」の方法は何であるかということです

編集:OK、アンドレアスのソリューションは非常に優れていますが、遅いです。それを改善する方法はありますか？

このアルゴリズムの Ruby バージョンをネットからかき集めるのではなく、ここでの説明に基づいて独自のアルゴリズムを作成したいと考えました。しかし、私は2つのことを理解できません

1. 配列の最後まで反復しないのはなぜですか?
2. 上記のリンクの説明によると、配列内の最後の要素の平方根が現在の素数よりも大きい場合、ループを解除する必要があります-私の前にこれを行います。

配列の長さを変更する削除操作と関係があると確信しています。たとえば、私の関数は現在 n=10 を入力すると 2,3,5,7,9,10 を生成しますが、これは明らかに正しくありません。これを変更して、想定どおりに機能させる方法について何か提案はありますか?

注:以下のバージョン 2 では、エラトステネスのふるいを使用しています。私が最初に尋ねたことに役立ついくつかの回答があります。エラトステネスの篩法を選択して実装し、質問のタイトルとタグを適切に変更しました。助けてくれたみんなに感謝します！

序章

指定された上限よりも小さい素数を含む int の配列を生成する、この手の込んだ小さなメソッドを作成しました。とてもよく効きますが、気になることがあります。

メソッド

私の懸念

私の懸念は、メソッドが返す要素の最終的な数に対して大きすぎる配列を作成していることです。問題は、指定された数よりも小さい素数の数を正しく推測する良い方法がわからないことです。

集中

これは、プログラムが配列を使用する方法です。これは私が改善したいものです。

1. 制限未満のすべての数値を保持するのに十分な大きさの一時配列を作成します。
2. 生成した数を数えながら、素数を生成します。
3. 素数だけを保持するのに適切な次元の新しい配列を作成します。
4. 巨大な配列から各素数を正しい次元の配列にコピーします。
5. 生成した素数だけを保持する正しい次元の配列を返します。

質問

1. 両方の配列を反復処理して要素を 1 つずつコピーすることなく、temp[]ゼロ以外の要素を持つチャンク全体を (一度に) コピーできます か?primes[]
2. インスタンス化時に次元を要求するのではなく、要素が追加されるにつれて成長できるプリミティブの配列のように動作するデータ構造はありますか? プリミティブの配列を使用する場合と比較して、パフォーマンスはどの程度低下しますか?

バージョン 2 ( Jon Skeetに感謝):

エラストステネスのふるいを使用するバージョン 3 ( Paul Tomblinに感謝) :

私は現在プロジェクトを行っており、素数を計算するための効率的な方法が必要です。私はエラトステネスのふるいを使ったことがありますが、いろいろと調べてみたところ、アトキンのふるいの方が効率的であることがわかりました。この方法の説明 (私は理解できました!) を見つけるのが難しいことがわかりました。それはどのように機能しますか？サンプル コード (できれば C または python) はすばらしいでしょう。

編集:ご協力ありがとうございます。私がまだ理解していないのは、疑似コードで x 変数と y 変数が参照しているものだけです。誰かが私のためにこれに光を当てることができますか?

私はエラトステネスのふるいを使ってスフィアのオンラインジャッジプライムジェネレーターを解いています。

私のコードは、提供されたテストケースで機能します。しかし..問題が明確に述べているように：

入力は、1行のテストケースの数tから始まります（t <= 10）。次のt行のそれぞれに、スペースで区切られた2つの数値mとn（ 1 <= m <= n <= 1000000000、nm <= 100000）があります。

非常に大きな数を処理するときにメソッドInteger.parseInt()が例外をスローし、オンラインジャッジが例外がスローされていることを示していたので、コード内のすべてのケースparseIntをに変更しました。parseLong

さて、mとnの値が小さいNetbeans6.5では問題なく動作しています。

入力+出力：

しかし、JCreatorLEはこれを言っています：

ここでは整数のオーバーフローはありませんが、なぜjcreatorが文句を言うのでしょうか。

境界テストケースを考慮すると、プログラムはNetbeansにも影響を及ぼします。

問題ステートメントのこれらの巨大な整数をどのように処理できますか？

編集：提案により、BitSetのブール配列を変更しましたが、まだOutOFMemoryError：を取得しています。

入出力：

上記のプログラムで n=100000 のとき、実行時間は 0.015 秒でした。また、C でエラトステネスのふるいアルゴリズムを実装したところ、n=100000 の実行時間は 0.046 でした。

上記のアルゴリズムは、実装した Sieve のアルゴリズムよりも高速です。

上記のプログラムの時間計算量は??

私のふるいの実装

私はいくつかの検索を行いましたが、この実装と私が見た他のすべての実装に関する情報を見つけることができませんでした.

ええ、私はそれを印刷するだけだと知っていますが、それは重要な部分ではありません. それが時間であろうとなかろうと、主な落とし穴は何ですか?

編集: スケーラビリティ以外の問題はありますか? また、主要な発見を進めることについてのコメントにも感謝します。

問題: 200 万以下の素数の合計を求めよ.

私はエラストテネスのふるいのことをほとんどやりました。以下のプログラムは小さな数で動作するようです。つまり、10L が答えとして 17 を生成するように LIMIT を定義します。

次のプログラムによって生成された 1179908154 を回答として提出しましたが、それは正しくありませんでした。

問題の指摘にご協力ください。ありがとう。