問題タブ [factorization]

ライブラリの場合、最初の素数を制限 L まで格納する必要があります。このコレクションには O(1) ルックアップ時間が必要であり (数値が素数かどうかを確認するため)、数値が与えられれば簡単でなければなりません。次の素数を見つけます (L より小さいと仮定します)。

L が固定されている場合、リストを生成するためのエラトステネふるいは問題ありません。現在、パックされたブール配列を使用してリストを保存しています。これには、3 から L (両端を含む) までの奇数のエントリのみが含まれています。これには (L-2)/2 ビットのメモリが必要です。より多くのメモリを使用せずに L を静的に増加できるようにしたいと考えています。

同様のプロパティでメモリ使用量が少ないデータ構造はありますか? または、少なくとも一定のルックアップ時間で？(素数が得られるまで、奇数を列挙できます)

（私がこれを書いた言語はFactorですが、この質問は、組み込みまたは簡単にプログラム可能なパックビット配列を持つ言語でも同じです）

私はプロジェクトオイラーで質問266を行っていますが、少し検索した後、数値の因数をすばやく見つけるこの方法を見つけました。あなたがすることは、数の素因数のすべての順列を見つけることです：これらはその因数です。

私はすでに数の素数冪係数を見つけるためのモジュールを持っています、例えば：

これは基本的に次のことを示しています2^2 * 7^2 == 196。ここから、これらの力のすべての順列を見つけて、196の因数をこのように与えたいと思います。

• （2 ^ 0）（7 ^ 0）= 1
• （2 ^ 1）（7 ^ 0）= 2
• （2 ^ 2）（7 ^ 0）= 4
• （2 ^ 0）（7 ^ 1）= 7
• （2 ^ 1）（7 ^ 1）= 14
• （2 ^ 2）（7 ^ 1）= 28
• （2 ^ 0）（7 ^ 2）= 49
• （2 ^ 1）（7 ^ 2）= 98

私は次のことを思いついた：

しかし、私の問題はそれfactorsが正しく機能しないことです。各素因数の指数の可能なすべての値を調べてから、因数を与える積を見つけたいと思います。nの因数だけを返すように変更するにはどうすればよいですか？

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

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

600851475143 の最大の素因数は?

考慮すべき事項:

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

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

アップデート

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

アップデート

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

Amicable Pairs を見つけようとするプログラムを作成しました。これには、数の適切な約数の合計を見つける必要があります。

これが私の現在のsumOfDivisors()方法です：

そのため、多くの因数分解を行う必要があり、それが私のアプリケーションの本当のボトルネックになり始めています。MAPLE に膨大な数を入力したところ、非常に高速に因数分解されました。

より高速な因数分解アルゴリズムの 1 つを教えてください。

C/C++ で Pollard Rho 整数因数分解を実装しようとしています。Google は、ここで問題の Java 実装を提供してくれます。

私はJavaをよく知らないので、これを思いついた.C ++での私の実装はほとんどの場合で機能しますが、「9999」のようにいくつかでは機能しません。

C++ には Biginteger クラスがなかったことを認識しているため、JAVA で提供されるすべての機能を使用することはできませんが、十分な 15 桁の数値を因数分解したいと考えています。unsigned long long

私の実装で何が間違っているかを指摘してください。

私はPythonで暗号化スキームをシミュレートしています。私はそれに対する新しいユーザーです。

p = 512ビット数であり、その最大の素因数を計算する必要があります。私は2つのことを探しています。

1. この大規模な素因数分解を処理するための最速のコード
2. 512ビットの数値を入力として受け取り、それを処理できるコード。

私は他の言語でさまざまな実装を見てきました。私のコード全体はPythonであり、これが私が立ち往生している最後のポイントです。それで、Pythonに実装があるかどうか教えてください。

私はPythonの新規ユーザーなので、簡単に説明してください

英語が下手でごめんなさい。

編集（以下のOPの回答から取得）：

上記のコードは「1238162376372637826」に対して（少し遅れて）機能しますが、

10902610991329142436630551158108608965062811746392 57767545600484549911304430471090261099132914243663 05511581086089650628117463925776754560048454991130443047

Pythonを狂わせます。上記のように、すぐに計算してもらう方法はありますか？

In class we found this programming problem, and currently, we have no idea how to solve it.

The positive integer n is given. It is known that n = p * q, where p and q are primes, p<=q and |q-k*p|<10^5 for some given positive integer k. You must find p and q.

Input:

Output:

It's not homework, we are just trying to solve some interesting problems. If you have some ideas, please post them here so we can try something, thanks.

私はプロジェクトオイラーの問題を解決することでルビーを学び、実践しています。

これが問題12の私の解決策です。

このコードに加えることができる改善はありますか？

あるものが別のもので割り切れるとき、数のビット間に何らかの関係がありますか？36のビットと9または4または12のビットシーケンスの間、または10（1010）と5（101）の間、または21（10101）と7（00111）の間の関係は何ですか？

ありがとう。文章がおかしいと申し訳ありませんが、ご理解いただければ幸いです。

私は整数の因数分解を必要とするプロジェクトオイラー問題に取り組んでいます。与えられた数の因数であるすべての素数のリストを思いつくことができます。算術の基本定理は、このリストを使用して、数のすべての要素を導き出すことができることを意味します。

私の現在の計画は、基本素数のリストの各数値を取得し、各素数の最大指数を見つけるための素因数がなくなるまでその累乗を上げることです。次に、素数と指数のペアの可能なすべての組み合わせを乗算します。

たとえば、180の場合：

次に、これらのすべての組み合わせを最大指数まで実行して、係数を取得します。

したがって、要因のリスト= [1、2、3、4、5、6、9、10、12、15、18、20、30、36、45、60、90、180]

これが私がこれまでに持っているコードです。2つの問題：最初に、それはまったくPythonicではないと思います。それを直したいのですが。第二に、私には、組み合わせの2番目のステップを実行するためのPythonの方法が本当にありません。恥ずかしさから、私はあなたをばかげたループのセットから免れました。

nは因数分解したい数です。listOfAllPrimesは、1,000万までの素数の事前計算されたリストです。