問題タブ [wheel-factorization]

ウィキペディアの車輪の因数分解の手順に従っていると、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 未満の他の素数は削除すべきではなかったのでしょうか?

私はかなり高速な素数ジェネレーターを実装しており、 Eratosthenes のふるいでいくつかの最適化を行って、いくつかの素晴らしい結果を得ました。特に、アルゴリズムの準備段階では、次のように 2 と 3 の倍数をすべてスキップします。

これは、エラトステネスのふるいm_sieveによるブール配列です。これは素数 2 と 3 のみを考慮した一種の Wheel 因数分解であり、パターン 2、4、2、4、.. に従って増加していると思います。

私がやりたいことは、おそらく素数 2、3、および 5 を考慮して、より大きなホイールを実装することです。

私はすでにそれに関する多くのドキュメントを読みましたが、エラトステネスのふるいを使用した実装は見当たりませんでした...サンプルコードは大いに役立ちますが、いくつかのヒントも役立ちます:)ありがとう。

ふるいをさらに最適化したい。私はすでにhttp://en.wikipedia.org/wiki/Wheel_factorization#Procedureから車輪の因数分解を学びました。しかし、ふるいにホイール分解を実装する方法がわかりませんか?

私の先生は私にこれをくれました：

n<=10^6;

n 整数の配列 :ai..an(ai<=10^9);

すべての素数を見つけます。

彼はエラトステネスのふるいについて何か言いました、そして私はそれについて読みました、また車輪の因数分解も読みましたが、プログラム（fpc）を1秒で実行する方法をまだ理解できませんでした.?? 私はそれが不可能であることを知っていますが、それでもあなたの意見を知りたい. ホイールの因数分解では、2*3 の円は 25 を素数として扱います。素数として誤って処理されたホイールの最初の数を見つける方法があるかどうか尋ねたいと思います。例: 2*3*5 円 、素数として扱われる最初の合成数を見つける方法?? 助けてください..そして悪い英語でごめんなさい。

いくつかのオイラーの苦労の一環として、因数分解ホイールを使用してエラトステネスのふるいをコーディングしようとしています。これまでの私のコードは次のとおりです。

ホイールが 6 要素よりも長い場合、次の結果が得られました。理由がよくわかりませんでした：

それ以外の場合、アルゴリズムは正常に機能しているようで、要素が 6 以下のホイールで素数を生成します。

長いリストが渡されると、明らかにapply、またはring鼻を上げます。

しかし、リストは単一の引数として数えるべきではないでしょうか? 私は完全に困惑していることを認めます。どんな入力でも大歓迎です。

これは技術的には車輪の因数分解だと思います。プログラムのエラトステネスの篩の表現を再圧縮しようとしています。これには、素数である可能性のある数値のインデックスのみが含まれています。

背景:

最も基本的なホイールは [2] です: 最初の素数として 2 を追跡し、ふるいには奇数インデックスのみが含まれます。(50%))

次のホイールは [2 3] です: 最初の素数として 2 と 3 を追跡し、ふるいには 2*3=6 (つまり、1 と 5) の間のギャップのみが含まれます。インデックスの形式は 6k+1 および 6k+5 です。(33%)

次のホイールは [2 3 5] です: 最初の素数として 2、3、および 5 を追跡し、サイズ 30 の間隔を表すためにふるいに必要なのは 8 ビットのみです。 (27%)

数値の倍数のビットをクリアするとき、次のループを使用してそれらの倍数を見つけます。

問題は、ホイールのセットアップにかかる時間と、圧縮比の収穫逓減です。それと rn を別のホイール サイズに変更するには、多くの再計算が必要です。また、ホイールのサイズを変えることで、漸近的な複雑さに影響を与えることができると思います。

したがって、私の提案する解決策は、小さなホイールを使用して大きなホイールを初期化することです。 [2 3 5 7] (210/48) ホイール

助けが必要なのは、計算済みの小さなふるいを、これから計算される大きなふるいにマッピングすることです。これにより、すべてを 1 から再ふるい分けすることを避けることができます。最初の 30 個の素数を取得し、それらを使用して次の 210 ～ 30 個の素数を見つけます。それらを使用して、次の 480-210 素数を見つけます。

より具体的には、この関数を反転する (または invIndexOf() を正しく実装する) 助けが必要です。

また、何かの漸近的な複雑さを理解してから数年が経ちました。劇的な改善ではありませんが、これは改善であると確信しています。