考慮すべきことは、64 ビットの符号なし整数をその素因数に (比較的迅速に) 因数分解するために使用できる次の関数です。因数分解は確率論的ではない (つまり、正確である) ことに注意してください。このアルゴリズムは、最新のハードウェアでは、数秒で数が素数であるか、非常に大きな因数がほとんどないことを検出するのに十分な速さです。

質問: できれば確率論的アプローチ (例: Miller-Rabin) を使用せずに、非常に大きな符号なし 64 ビット整数を (任意の) より高速に因数分解できるように、提示されたアルゴリズムをシングル スレッドに保ちながら、何らかの改善を行うことはできますか?素数を決定するため？

ありがとう

編集：さらにコメントを追加しました。ベクトルが参照によって渡される理由は、呼び出し間でベクトルを再利用できるようにし、動的な割り当てを回避するためです。関数内でベクトルが空にならない理由は、現在の「num」の係数をベクトル内に既にある係数に追加するという奇妙な要件を考慮に入れるためです。

関数自体はきれいではなく、リファクタリングできますが、問題はアルゴリズムを高速化する方法です。したがって、関数をより見やすく、読みやすく、または C++ 風にする方法についての提案はありません。それは子供の遊びです。このアルゴリズムを改善して、(証明された) 因子をより速く見つけられるようにすることは、難しい部分です。

更新: Potatoswatterはこれまでにいくつかの優れたソリューションを提供しています。下部にある彼の MMX ソリューションも必ずチェックしてください。

これは私が現在持っているコードですが、DrJavaで数分間実行しましたが、結果が返されませんでした。私のコードを最適化する方法はおよそ100万通りあると思いますが; 誰かが私にいくつかのヒントを与えることができますか？

今日、いくつかのプログラミングの問題を解決しようとしていますが、これは私にいくつかの問題を引き起こしています。

どうもありがとう ：）

C＃でモジュロを使用して、数値の最大の素因数を見つけることができるかどうか疑問に思っていました. 言い換えれば、ループなどi % x == 0を破ることができれば、ここでは値を下回るすべての自然数に等しくなります。forxi

all natural numbers below our i valuex 変数に等しいと指定するにはどうすればよいでしょうか。私が言っていることを知っていれば、整数ごとに条件を書き出すのは少し面倒です。

ところで、C# でこれを行うにはもっと簡単な方法があると確信しているので、アイデアがあれば教えてください。私の初心者の知識でそれができれば。

私がこれまでに持っているものを確認したい場合は、これが私の現在のコードです。

そのため、私は Haskell を学習している最中であり、型/型クラス関連のエラーに陥ることがよくあります。かなり明らかなばかげた間違いもあれば、haskell が自分にはふさわしくないと感じさせるものもあります。とにかく、私はこのコードを持っています...

(いくつかの背景: pfactors 関数は、数値を取り、指定された数値の素因数である素数のリストを返すことになっています。primes素数の無限リストです)

これは私にこのエラーを与えます:

p < (sqrt n)と関係のある唯一のパーツであるため、これはパーツの問題であることがわかりましたFloating。すべてに変更すると正常にp < n動作し、正しい答えが得られます。でもどうしても平方根で確認したいのですがどうすればいいですか？

ところで、これは宿題ではありません。気が付けば、projecteuler.net の 47 番目の問題を解決しようとしているところです。

助けてくれてありがとう。

そして、上記のプロジェクトオイラー問題の解決策を私に教えないでください。私はできる限り自分でやりたいです:)。ありがとう。

Python、疑似コード、またはその他の読みやすいものでNの素因数を取得するための実装または明確なアルゴリズムを探しています。いくつかの要件/制約があります。

• Nは 1 ～ 20 桁です
• 事前に計算されたルックアップ テーブルはありませんが、メモ化は問題ありません
• 数学的に証明する必要はありません (たとえば、必要に応じてゴールドバッハ予想に頼ることができます)。
• 正確である必要はありません。必要に応じて確率論的/決定論的であってもかまいません。

それ自体だけでなく、オイラーphi(n)の計算など、他の多くのアルゴリズムで使用するための高速な素因数分解アルゴリズムが必要です。

ウィキペディアなどから他のアルゴリズムを試してみましたが、理解できなかった (ECM) か、アルゴリズムから機能する実装を作成できませんでした (Pollard-Brent)。

私は Pollard-Brent アルゴリズムに非常に興味を持っているので、それに関する情報や実装があればとてもうれしいです。

ありがとう！

編集

少しいじった後、かなり高速な素数/因数分解モジュールを作成しました。これは、最適化された試行分割アルゴリズム、Pollard-Brent アルゴリズム、Miller-Rabin 素数性テスト、およびインターネットで見つけた最速の素数ふるいを組み合わせたものです。gcd は通常の Euclid の GCD 実装です (バイナリ Euclid の GCD は通常のものよりもはるかに遅いです)。

バウンティ

なんと、バウンティを獲得できます！しかし、どうすれば勝つことができますか？

• モジュールで最適化またはバグを見つけます。
• 代替/より優れたアルゴリズム/実装を提供します。

最も完全で建設的な回答が賞金を獲得します。

そして最後にモジュール自体:

私はプロジェクトのオイラー数を Scala で 3で解こうとしていますが、これがこれまでのところ得たものです。

これはうまくいくと思いますが、私は仕事で立ち往生しており（遅いビルド中に時間を利用しています）、SimplyScalaサービスしかありません-タイムアウトしています（自宅で確認します）。

しかし、これは私が書いた Scala の最初の部分なので、私はどんな恐ろしい罪を犯したのでしょうか? 私の解決策はどれほど絶望的に最適ではないでしょうか? 私が踏みにじった慣習は何ですか？

ありがとう！

私はオイラープロジェクト3の解決に取り組んでいます。

これは答えを生成するための私のコードです。ただし、を保持するには整数型が必要600851475143です。MacのGCCでこれをコンパイルすると、次のようになります。

長い間、この数を簡単に保持できると思います。また、署名なしにしてみました。なぜ私のコードはその小さな数を保持しないのですか、そしてそれを機能させるために何ができますか？

パラメータで渡された整数のすべての素数要素を見つけるために、Javaで単純なアルゴリズムを実装しようとしています:

面白いことに、n として 81 を渡すと、結果は 3, 3, 3, 3, 3, 3, 3, 3 になり、3, 3, 3, 3 (3^4=81) となるはずです。

この興味深いアルゴリズムをできる限り改善しようとしています。

今のところ、私はこれを持っています：

アイデアはありますか？

ありがとう！

EDIT：Benのアルゴリズムを実装しました。助けてくれてありがとう！

宿題では、正確に 7 つの約数を持つ 1 から 1000 までの一連の数字を見つけるロジックが必要です。

(理想的には、素数を生成するようにコードを簡単に変更できます。)