問題タブ [primes]

数年前、 PRIMES が Pにあることが証明されました。Python で素数性テストを実装するアルゴリズムはありますか? 単純なジェネレーターでいくつかのベンチマークを実行し、それがどれほど速いかを自分で確認したかったのです。私はそれを自分で実装しますが、それを行うには論文をまだ十分に理解していません。

クリスマスプレゼントとして、素数を計算するための小さなプログラムをJavaで作成しました。私の意図は、それを一晩中置いておき、次の素数を計算して.txtファイルに書き込むことでした。朝、私はプログラムを終了し、クリスマスのために.txtファイルを友達に持っていきました。

気になることはありますか？これはあなたが話している真の初心者のZiggyであり、ASMの人をチェックする賢いエラーではないことを覚えておいてください。

編集より具体的には、私はこのプログラムを一晩中素数を数えることにしているので、ある種のメモリ関連のエラーに遭遇する可能性はありますか？積み重ねて山を砕いたり、犬や猫が一緒に寝たりしますか？

さらに具体的に編集すると、ファイルのサイズが4GBのときに行の印刷を停止するために入力できるコード行はありますか？安全のためだけに？

編集：成功：一晩中それを残した後、私は13 KBの素数しか得られませんでした、私が得た最高は22947217で、これは数万の素数のようなものです。成功！

暗号学者ではない私をいつも驚かせることの 1 つは、素数を使用することがなぜそれほど重要なのかということです。それらが暗号化においてそれほど特別な理由は何ですか?

誰か簡単な短い説明がありますか? （多くの入門書があり、応用暗号が聖書であることは承知していますが、前述のとおり、私は独自の暗号アルゴリズムを実装するつもりはありません。見つけたものは私の脳を爆発させました.10ページの数式はありません.お願いします ：））

すべての答えをありがとう。実際のコンセプトを最も明確にしてくれたものを受け入れました。

C ++を使用して素数を見つけるための最速のアルゴリズムはどれですか？私はふるいのアルゴリズムを使用しましたが、それでももっと速くしたいです！

現在、プログラミングスキルを練習するためだけに、いくつかの質問を試しています。（学校などでまだ取っていません、独学です）この問題に遭遇したため、特定のtxtファイルから数値を読み取る必要がありました。この数は N になります。ここで、N <= 10 000 の N 番目の素数を見つけるとします。見つけたら、それを別の txt ファイルに出力するとします。これで、質問のほとんどの部分で、N を取得する方法を理解し、考案することができました。問題は、配列を使用して以前に見つかった素数を保存し、それらを使用して将来の数と照合することです。配列のサイズが 100 の場合でも、入力整数がおおよそ < 15 である限り、プログラムはクラッシュします。

私はこれを完全に私のダミーガイドと私自身に基づいて行ったので、コードの非効率性とアルゴリズムの一般的な初心者性を許してください。また、15 までは素数を正しく表示します。

この現在のコードを改善するにはどうすればよいか、誰か教えてもらえますか? 配列の代わりにtxtファイルを使用することを考えています。それは可能ですか？どんな助けでも大歓迎です。

誰かが私がこのコードで間違っていることを教えてもらえますか? とにかく「カウント」を印刷しているだけです。私は非常に単純な素数ジェネレーターが欲しいだけです（派手なものは何もありません）。

私は Project Euler の問題 27を解決しようとしてきましたが、これは私を困惑させているようです。まず、コードの実行に時間がかかりすぎます (私のマシンでは数分かかるかもしれませんが、もっと重要なのは、しばらく調べてもアルゴリズムに問題があることを実際に見つけることができませんが、間違った答えを返すことです)。 .

これが私の現在のソリューションのコードです。

a）このアルゴリズムが実際に正しい答えを返すようにする方法に関するヒント（少なくとも実行可能なアプローチを取っていると思います）およびb）プロジェクトで設定された「1分間のルール」を明らかに超えているため、パフォーマンスを改善しますオイラーFAQ. 私は関数型プログラミングの初心者なので、より機能的なソリューションを念頭に置いて問題をどのように検討するかについてのアドバイスもいただければ幸いです。

17 と同様に素数、逆にすると 71 も素数です。

なんとかこのコードにたどり着きましたが、完成させることはできません。

私の問題は、すべてのfを追加する方法です..

答えは 429 です。

すべての f を追加するにはどうすればよいですか?

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

序章

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

メソッド

私の懸念

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

集中

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

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

質問

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

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

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

いくつかの素数関連のメソッドを含む小さなライブラリを作成しています。私は基礎（別名作業方法）を行ったので、今はいくつかの最適化を探しています。もちろん、インターネットはそうするのに最適な場所です。しかし、丸めの問題に遭遇し、これを解決する方法を考えていました。

数の素数をテストするために使用するループでは、n/2 または n - 1 の代わりに sqrt(n) まで検索する方が効率的です。たとえば、10000 番目の素数は 104729 のはずですが、「最適化された」バージョンは 103811 になります。

いくつかのコード (より多くの最適化のために開いていることは知っていますが、一度に 1 つのことしか処理できません):

2乗部分が失敗する（または失敗する）ことを知っており、Math.Ceilingも試してみましたが、ほぼ同じ結果が得られました。