問題タブ [sieve]

N 番目の素数を見つけることの逆を行う必要があります。つまり、素数が与えられた場合、その位置を見つける必要があります。

素数は のオーダーで大きくなる可能性があり10^7ます。また、それらの多くがあります。

二分検索できる事前計算された素数のインデックスがありますが、50k のスペース制限もあります。ふるい分けはできますか？または別の高速な方法はありますか？

編集：すべての素晴らしい回答に感謝します。私はそれらを期待していませんでした! 同じものを探している他の人に役立つことを願っています。

最初の100個の素数を出力しようとしていますが、エラーが発生し続けます。

アプリケーション：手順ではありません。与えられた引数に適用できるプロシージャが必要です：（＃）引数...：[なし]

エラーは、ここのtake$プロシージャに表示されます。

ここにすべての私のコードがあります：

あなたが提供できるどんな助けにも感謝します。

このプログラムは、エラトステネスのふるいを使用して素数を計算するc++プログラムです。次に、これを行うのにかかる時間を保存し、計算を100回再実行して、毎回時間を保存することになっています。このプログラムで私が助けを必要としていることが2つあります。

第一に、私はそれより高くなりたい4億8000万までの数しかテストできません。

第二に、私がプログラムの時間を計るとき、それは最初のタイミングだけを取得し、次に時間としてゼロを出力します。これは正しくなく、時計の問題が何であるかわかりません。-助けてくれてありがとう

これが私のコードです。

私はふるいを働かせようとして立ち往生しています。デバッグすると、9 や 15 のようなものがふるいを通過しても true と評価されることがわかります。これは何が原因ですか？また、ベクトルを適切に使用して最高の素因数を取得していますか?

さて、私が作成したこの関数は、エラトステネスのふるいアルゴリズムを使用して、すべての素数 <= n を計算します。この関数は、素数と素数の数をパラメーターに格納します。

関数が終了するとき、素数は、すべての素数 <= num を保持する、動的に割り当てられたメモリのチャンクを指している必要があります。 *count素数の数になります。

ここに私の機能がありますgetPrimes:

さて、これが意図した出力と私の出力です。getPrimesご覧のとおり、関数内で何か問題が発生していますが、何が問題なのかわかりません。

これまでに人々が私に指摘した3つの問題は次のとおりです。

1. 間違った削除プロセスif (sieve[multiple]) {配列ふるいインデックスにバイアスがあります
2. (*array) = sieve;ちょうどmallocされたメモリをリークし*array、関数が戻ったときに存在しなくなるローカル変数を指すようにします-ダングリングポインターを取得します.
3. if(sieve[i] != NULL)NULLではなく0を使用する必要があります。ポインターの配列がありません。

ただし、発見されたぶら下がっているポインター/メモリの問題を修正する方法がよくわかりません。それに加えて、出力の数字に0が追加されている理由がよくわからないため、コード内にエラーのあるものが他にあるかどうか疑問に思っていました...別の出力スタイルについて心配する必要はありません。余分な数字だけです. これで私を助けてくれてありがとう！

さて、私が作成したこの関数は、エラトステネスのふるいアルゴリズムを使用して、すべての素数 <= n を計算します。この関数は、素数と素数の数をパラメーターに格納します。

関数が終了するとき、素数は、すべての素数 <= num を保持する、動的に割り当てられたメモリのチャンクを指している必要があります。*count には素数の数が含まれます。

ここに私の関数 getPrimes があります:

ここでの関数は完全にコンパイルされますが、101 などの大きな数値を試してみると、セグメンテーション違反があることに気付きました。私のコードがセグメンテーション違反を引き起こしている場所を誰かが見ていますか?

以下の 2 つの関数は完全にコンパイルされますが、最初に入力された整数で奇妙なエラーが発生しているようです。私は GDB でデバッグを試みましたが、この奇妙なエラーが最初に入力された値だけである場合、事態は複雑になります。

私たちのアウトプット:

予想される出力は明らかに 2 を表示するはずです。これは、最初に入力された整数の 2 ～ 2000 の整数の場合です。最後の、または最後の 2 つの素数は、非常に大きな数を出力し、時には負の数さえ出力します。理由はわかりませんが、最初に入力された値の後、すべてが完全に機能します。狂ったようにGDBでこれをデバッグしようとしましたが、うまくいきませんでした。この奇妙なエラーについて誰かの助けを本当に感謝します

私は Python を学ぼうとしていますが、自分のプライム シーブを開発することは、午後の興味深い問題になると思いました。これまでのところ、必要に応じて、オンラインで見つけたバージョンのエラトステネスのふるいをインポートするだけでした。これをベンチマークとして使用しました。

いくつかの異なる最適化を試した後、私はかなりまともなふるいを書いたと思いました:

最初の 1,000,000 個の整数を範囲として使用すると、このコードは正しい数の素数を生成し、ベンチマークよりも約 3 倍から 5 倍遅くなりました。諦めて背中を撫でようと思ってレンジを広げてみたらダメだった！

問題は の行にあると思いますが、[****]なぜそんなに壊れているのかわかりません。「j」の各奇数倍数を False としてマークすることになっており、ほとんどの場合は機能しますが、4,194,304 を超えるとふるいが破られます。（公平を期すために、たとえば10,000など、他のランダムな数字でも壊れます）。

変更を加えたところ、コードの速度が大幅に低下しましたが、実際にはすべての値で機能します。このバージョンにはすべての数字 (オッズだけでなく) が含まれていますが、それ以外は同一です。

元の関数 (sieve3) が一貫して機能しない理由を理解してくれる人はいますか?

編集：Sieve3が「壊れる」と、sieve3（n）がn / 2を返すことを忘れていました。

演習として書いている RSA 実装の素数性テストを実装しようとしています。私は主に Rabin-Miller を使用していますが、1,000 未満のすべての素数のリストを定式化するエラトステネスのふるいを持っており、候補者がそのうちの 1 つを素因数として持っているかどうかを判断するための簡単なテストに使用します。

関連する機能は次のとおりです。

ここで、primeList は Sieve によって生成された素数のリストです。これは 2^55 程度の to_test 値までは完全に機能しますが、それを超えると、

このステートメントは、Rabin-Miller が素数であると判断した to_test を渡した場合でも、常に 0.0 と評価されます。これが何であるかわかりません。Python が非常に大きな数をどのように処理するかについては明確ではありませんが、私の知る限り、2^55 はオーバーフロー ボーダーのようなものではないようです。Sieve を使用すると、関数が大幅に高速になり、2048 ビットの実装のキーを生成するにはしばらく時間がかかるため、これは演習ですが、Sieve が機能するかどうかを確認したいと思います。

前もって感謝します。

1 ～ n のすべての数に対して除数を数えるふるいを作成することはよく知られています。

しかし、1 * n の形式の数値のふるいを作成する代わりに、6n^2 の形式の数値の除数を計算したい場合はどうすればよいでしょうか?

したがって、1、2、3、4、5 などの除数カウントを見つける代わりに、6、24、54、96、150 などの除数カウントを探している可能性があります。

しかし、実際には効率的な方法で形式 kn^p の数だけであるため、実際にはサイズ kn^p の配列を最大で格納していません。以前のようにサイズ N の配列のみが必要なようです。各スポットのみが kn^p の約数を表します