問題タブ [sieve-of-atkin]

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

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

ここの誰かが共有したいアトキンのふるいの良い実装を持っているかどうか疑問に思いました。

私はそれを実装しようとしていますが、頭を完全に包むことができません。これが私がこれまでに持っているものです。

ウィキペディアにリストされている擬似コードを「翻訳」しようとしたところですが、正しく機能していません。ですから、私は何かを誤解したか、何か間違ったことをしただけです。またはおそらく両方...

テストとして使用する最初の500素数のリストがあり、実装は40番（または41番？）で失敗します。

値はインデックスで異なります[40]
期待値：179
しかし、だった：175

私の間違いを見つけることができますか、共有できる実装がありますか、またはその両方ですか？

私が使用している正確なテストは次のようになります。

これが可能かどうかはわかりませんが、質問する必要があります。私の数学的およびアルゴリズムのスキルは、ここで私を失敗させているようなものです:P

問題は、特定の制限まで素数を生成するこのクラスがあることです。

今、私が望むのは、シーケンスが（理論的に）決して停止しないように制限を取り除くことです。

私はそれが次のようになると考えています：

1. 些細な制限から始める
   • 極限までのすべての素数を見つける
   • 新たに見つかったすべての素数を生成する
   • 制限を増やす (古い制限を 2 倍または 2 乗するなどして)
   • ステップ 2 に進む

そして、最適には、そのステップ 2 は古い制限と新しい制限の間でのみ機能する必要があります。言い換えれば、最低の素数を何度も見つける必要はありません。

これを行う方法はありますか？x私の主な問題は、yたとえばこのアルゴリズムの内容がよくわからないことです。同様に、同じ種類のアルゴリズムを使用して、xandyをoldLimit(最初は 1) に設定し、それを まで実行できnewLimitますか? または、それはどのように機能しますか？これに光を当てる明るい心はありますか？

これのポイントは、その制限を設定する必要がないようにすることです。たとえばTake()、制限が十分に高いかどうかなどを気にせずに、Linq と必要な数の素数を使用できるようにします。

最近、素数を生成するために Atkin のふるい ( http://en.wikipedia.org/wiki/Sieve_of_atkin ) を使用する C++ 素数ジェネレーターに取り組んでいます。私の目標は、任意の 32 ビット数を生成できるようにすることです。主にプロジェクトのオイラー問題に使用します。ほとんどは夏のプロジェクトです。

プログラムはビットボードを使用して素数を格納します。つまり、一連の 1 と 0 で、たとえば 11 番目のビットが 1、12 番目が 0、13 番目が 1 などになります。メモリを効率的に使用するために、これは実際にはおよび char の配列で、各 char には 8 ビットが含まれます。フラグとビットごとの演算子を使用して、ビットを設定および取得します。アルゴリズムの要旨は単純です。数値が「素数」と見なされるかどうかを定義するために、私が理解しているふりをしていないいくつかの方程式を使用して最初のパスを実行します。これでほとんどの場合正しい答えが得られますが、いくつかの非素数が素数としてマークされます。したがって、リストを反復処理するときは、見つけたばかりの素数のすべての倍数を「素数ではない」に設定します。これには、素数が大きくなるほど必要なプロセッサ時間が少なくて済むという便利な利点があります。

90% 完成しましたが、問題が 1 つあります。いくつかの素数が欠落しています。

ビットボードを調べたところ、最初のパスでこれらの素数が省略されていることがわかりました。これは基本的に、いくつかの方程式の解ごとに数値を切り替えます (ウィキペディアのエントリを参照)。私はこのコードのチャンクを何度も何度も調べてきました。ウィキペディアの記事に示されている範囲を広げてみましたが、これは効率的ではありませんが、何らかの形で省略したいくつかの数字にヒットする可能性があると考えました. 何も機能していません。これらの数値は、単純に素数ではないと評価されます。私のテストのほとんどは、128 未満のすべての素数で行われました。この範囲のうち、省略された素数は次のとおりです。

23と59。

より高い範囲では、より多くのものが欠けていることに疑いの余地はありません（それらすべてを数えたくないだけです）. これらが欠落している理由はわかりませんが、欠落しています。これらの 2 つの素数について特別なことはありますか? 私は二重、三重にチェックし、間違いを見つけて修正しましたが、それでも私が見逃しているのはおそらくばかげたものです。

とにかく、ここに私のコードがあります：

私はそれをきれいにして読みやすくするために最善を尽くしました。私はプロのプログラマーではありませんので、ご容赦ください。

pgen という名前の PrimeGen オブジェクトを初期化し、その初期ビットボードを pgen.printBoard() で出力し (next() 反復の前に 23 と 59 が欠落していることに注意してください)、次に next() を反復して得られる出力を次に示します。返された素数をすべて出力します。

私のSieveofAtkinの実装では、限界近くの素数または限界近くのコンポジットを見落としています。一部の制限は機能し、他の制限は機能しません。私は何が悪いのか完全に混乱しています。

たとえば、1000の制限まで素数を生成すると、アトキンのふるいは素数997を見逃しますが、複合965を含みます。しかし5000の制限まで生成すると、返されるリストは完全に正しいです。

エラトステネスのふるいを実装して、上限なしで連続的に素数を見つけることができるという事実を認識しています (セグメント化されたふるい)。

私の質問は、Atkin/Bernstein のふるいを同じ方法で実装できますか?

関連する質問: C#: Atkin のふるいをインクリメンタルにする方法

ただし、関連する質問には「すべてのふるいでは不可能です」という回答が1つしかなく、明らかに間違っています。

ウィキペディアでアトキンのふるいについて読んだことがありますが、現時点ではウィキは限られています。アトキンのふるいの概要とJavaの例を探していました。

ありがとう。

ユーザーが200万未満のすべての素数の合計を計算するように求められるプロジェクトオイラー問題10を解決しようとしています。ウィキペディアで疑似コードを調べて次のように書きましたが、入力しようとすると、少なくともウェブサイトによると、生成される答えは正しくないようです。

次の出力が生成されます。

手で確認できる小さな制限でテストしましたが、コードは実際にそれらの数値に対して正しく機能しています。答えが であるべきであることを示す他の人々の実装を見つけまし142913828922たが、彼らのコードが私のコードとどこが違うのかわかりません。

ここで私が間違っていることを誰かが見ることができますか?

私はエラトステネスのふるいを試しました：以下は私のコードです：

時間がかかりました：私のシステムでは実際の7.340秒です。

私はまた、アトキンのふるいを試しました（エラトステネスのふるいよりも速くどこかで勉強しました）。

しかし、私の場合は時間がかかりました：実際の10.433秒。

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

さて、1秒間に100万個の素数を出力できるものはないのだろうか。

1つのアプローチは次のとおりです。

誰かが私に最初の100万の素数をより少なくする方法を提案してもらえますか

制約を満たす秒よりも（上記で説明）？

ありがとう!!

そこで、素数を生成するアトキンアルゴリズムのふるいを作成しました (プロジェクト オイラーの問題用)。という素数 (int[]) の配列を返しますprimes。問題は、あるインデックスからその配列にアクセスしようとするたびに (mainメソッドでそうする)、例外がスローされることですjava.lang.ArrayIndexOutOfBounds。助けてください（そして、私の論理が妖精と離れていると思われ、これを行う簡単な方法があると思われる場合は、教えてください）！