問題タブ [primes]

私は非常に大きな数の最大の素因数を見つけるプログラムを書こうとしていますが、さまざまな成功を収めたいくつかの方法を試しました。私がこれまでに見つけたものはすべて、信じられないほど遅いものでした。私は考えましたが、これが有効なアプローチであるかどうか疑問に思っています。

このアプローチは入力を受け取り、次のことを行います。

200-> 100-> 50-> 25-> 5（リターン）

90-> 45-> 15-> 5（リターン）

currentNum自体が素数になるまで（ほとんどの場合2、または3）、currentNumを最小の除算数（ほとんどの場合2、または3）で繰り返し除算し、これが元の入力の最大の素因数であると想定します。

これは常に機能しますか？そうでない場合、誰かが私に反例を与えることができますか？

-

編集：非常に大きいとは、約2 ^ 40、つまり10^11を意味します。

この問題は少し奇妙に感じました。データベース内の素数のリストをどのように表現できるか興味があります。大量の素数を正確かつ一貫して格納できる単一のデータ型を私は知りません。私の懸念は、素数に数千桁が含まれるようになると、データベースから参照するのが少し難しくなる可能性があることです。DB で素数の大きなセットを表す方法はありますか? このトピックには以前にアプローチしたことがあると確信しています。

これを難しくしている問題の 1 つは、素数を約数に分解できないことです。彼らができれば、この問題ははるかに簡単になります。

メソッドを使用して、配列からすべての素数を出力したいと思います。1 つの int で実行できますが、配列から特定の数値を返す方法がわかりません。手伝ってくれてありがとう！

お二人ともありがとう。解決したようです：

問題は、1000 番目の素数を見つけることです。このために、次の python コードを作成しました。問題は、10 番目と 20 番目の素数について正しい答えが得られることですが、その後は 10 ずつインクリメントするたびに 1 つずれてしまいます。ここでバグをキャッチできません:(

ご参考までに、素数として 2 をテストしていないため (私は 3 から始めています)、count は 1 として初期化され、candidate奇数のみが素数になる可能性があるため 2 ずつインクリメントされます。素数定理など、この問題を解決する他の方法があることは知っていますが、このアプローチの何が問題なのか知りたいです。また、考えている最適化があれば、提案してください。

ありがとうございました

私は F# を学ぼうとしているので、 Project Eulerを訪れ、現在問題 3に取り組んでいます。

13195 の素因数は 5、7、13、29 です。

600851475143 の最大の素因数は?

考慮すべき事項:

1. 私の最優先事項は、良い機能的な習慣を身につけることです。
2. 私の 2 番目の優先事項は、高速で効率的であることです。

次のコード内で、この質問に関するセクションをマークしました。

アップデート

いくつかのフィードバックに基づいて、コードをリファクタリングして 10 倍速くしました。

アップデート

アドバイスをくれた皆さんに感謝します。この最新版は、私が受けたすべてのアドバイスをまとめたものです。

これは私が思いつくことができる最高のアルゴリズムです。

さらに速くすることはできますか？

このコードには欠陥があります。numbersは順序付けられていないセットであるnumbers.pop()ため、セットから最小の番号を削除する保証はありません。それにもかかわらず、それはいくつかの入力番号に対して（少なくとも私にとっては）機能します：

これがspoj素数ジェネレーターの私のコードです。
Altoughtは、別の受け入れられたコードと同じ出力を生成します。

出力は 12 が素数であることを示していますが、それが間違っていることはわかって
います。

最近、素数を生成するために 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() を反復して得られる出力を次に示します。返された素数をすべて出力します。

私はパッケージjava.util.concurrentを初めて使用します。マルチスレッドとモノスレッドの戦略を使用して、数値が素数であるかどうかをテストする次のプログラムを作成しました。

メソッドloopMTの場合、パッケージjava.util.concurrentのクラスを使用する正しい方法ですか？このプログラムを書くための別の（より安全で、よりエレガントな）方法はありますか？マルチスレッド環境でSystem.outを使用できますか？

あなたの提案に感謝します

ピエール