問題タブ [sieve]

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

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

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

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

自然数系列では、1 回目のパスで 2 つおきの要素を削除する必要があります。次に、残りの要素で、2 番目のパスで 3 つおきの要素を削除します。次に、K 番目のパスで、残りの要素から (k+1) 番目の要素をすべて削除します。

シリーズはこうなる

1回目のパスの後（2つおきの要素を削除した後）、

2 回目のパスの後 (3 番目の要素をすべて削除した後)、

3 回目のパスの後 (4 つごとの要素を削除した後)、

したがって、無限パスの後、次のようになります

このシリーズはFlavius-Josephus sieveとも呼ばれます。

これに対する解決策は、シリーズの 6 番目の要素を見つけることです。

• 6^2 = 36 を行います
• 35 を与える 5 の倍数に下がる
• それから 4 の倍数 = 32 まで
• それから 3 の倍数 = 30 まで
• 次に 2 の倍数 = 28 まで
• 次に、1 = 27 の倍数まで
• したがって、6 番目のラッキー ナンバーは 27 です。

それは機能しますが、ソリューションがどのように機能するのか理解できませんか?

このためのACプログラムは、

これを説明するリンクhttp://oeis.org/A000960

ループ内の整数をalongとaの商と比較する必要がありlongます。整数除算を行わないために、私が正しく理解している場合、longの1つをdoubleに変換する必要がありますか？

これがコードスニペットです。primesはsで満たされた配列longです。ところで、このコードは正しいです：

long * int配列インデックスではが機能しないのではないかと心配しているからです。

本当にありがとう！

この[質問]:http://www.spoj.pl/problems/PRIME1/のセグメント化されたふるいアルゴリズムを次のように実装しようとしました:

それにもかかわらず、私はTLEを取得しています..他にどのような最適化が必要になるかわかりません。助けてください..

編集1：一定時間でfd_p（）を実装しようとしました... [失敗] ..このバグで私を助けることができれば..

編集 2: 問題が解決しました。

私は過去5時間コードを注ぎ込み、どこにも行き着きませんでした。コードを実行するたびに、セグメンテーション違反が発生します。クライアント側で発生することもあれば、サーバー側で発生することもあるので、何が起こっているのかわかりません。 このコードは、100までの素数を検索しようとすると機能しますが、それ以降は機能しません。私が最後にここに投稿したとき、私は完全なコードを投稿するように言われたので、ここにあります：

サーバ：

クライアント：

私はPythonでエラトステネスのふるいの実装を作成しています。発生する問題は、すべての素数（主に小さい番号の素数）が表示されるわけではありません。

これが私のコードです：

を入力>>> prevPrimes(1000)すると、結果は次のようになります。[2, 3, 5, 7, 11, 13, 17]など。ただし、次のようになります[1, 37, 41, 43, 47, #more numbers]。

False私のプログラムが素数をチェックする方法のために、問題は「元の」素数（2、3、5、7、11、13、17など）を示しているという事実にあることを私は知っています。どうすればこれを回避できますか？前もって感謝します ：）

私の入力はIntegerです。その値までは、すべての素数を見つけて5列に出力する必要があります。次に、整数を「素数分解」して結果を出力する必要があります。

それはうまくいきますが、遅すぎません...

}

どこでリソースを節約できますか？ところで、今のところ配列しか使えません...ドイツ語のコメントでごめんなさい。本当に不要な長いループなどが目に入った場合

ありがとう！

ウィキペディアのページで指定されている基本的なアルゴリズムに従って、Haskell に 2 次ふるいを実装しました。ほとんどの整数でうまく機能しますが、n乗である数値Nの因数分解を見つけることができません。偶数乗 (平方) の場合、アルゴリズムはループし、奇数乗の場合、N を法とする平方であるいくつかの滑らかな数を見つけます (私はこれをテストして確認しました)。些細な要因。

ウィキペディアのアルゴリズムを文字どおりに実装したことは十分に確信しています。n乗を処理できないバージョンのアルゴリズムに問題がありますか、それとも私のアルゴリズムにバグがありますか?

なんらかの理由で、 stackoverflowでコードのフォーマットに問題が発生しています。

Sieve of eulerは、 Sieve of Eratosthenesよりも漸近的な複雑さを備えており、命令型言語で簡単に実装できます。

ストリームを使ってエレガントに実装する方法があるかどうか疑問に思っています。素数についてhaskellwikiを確認しましたが、2つの実装はそのwikiの他のふるい（試行除算でさえ！）よりも数百倍遅いです。

だから私は自分で書こうとします：

minusに似てminusいData.List.Ordます。

takeWhile'に似てtakeWhileいますが、わずかな違いがありtakeWhileます。述語を満たさない最初の要素を削除します。takeWhile'それを取るでしょう。

lsp iiの積の有限ストリームを返し、iの最小素因数以下を素数にします。

悲しいことに、私の実装は信じられないほど遅くなります...そして私は犯人を見つけることができません。

とにかく、ストリーム処理スタイルでオイラーの効率的なふるいを実装することは可能ですか？または、アルゴリズムには、ストリームの性質に対して固有の影響がありますか？

リストにない可能性が最も高い特定の数に既存のリストをスライスする方法があるかどうか疑問に思っていました。たとえば、私が持っているとします：

ここで、数 11 の原始性をテストしたいと思います。1 + 11 の整数平方根の制限の下で、すべての素数による試験的な除算によってこれを行います。そのため、素数リストのすべての要素をループして要素が制限よりも大きくなったらループを破る代わりに、私はリストを Limit の値に接続できるかどうか疑問に思っていました。この場合、値は次のようになります。

primes[ : up until the value of 4]またはの要素をループできるように[2,3]

私はある程度のpythonを知っていますが、リストメソッドだけでこれを行う方法がわかりません...そして、数十億までのふるいメソッドについては、ifステートメントを使用しないことで効率的に時間を節約できました...

よろしくお願いします！