2

私は10^18のオーダーの数のすべての要因を見つけようとしています...しかし、問題を引き起こしている時間の制約があります。私がやったことは、エラトステネスのふるいを使って因子を見つけて保存することでしたが、それは遅いです......。

4

3 に答える 3

4

スペースに問題がない場合は、10 ^ 9までの素数のリストを保存し（リストはダウンロード可能）、それを使用して10^18までの任意の数を因数分解できます。素因数分解アルゴリズム（ポラードローなど）を使用することもできます。

于 2012-09-03T16:49:10.290 に答える
1

この整数因数分解に関するWikiの記事を読むことを強くお勧めします：http：//en.wikipedia.org/wiki/Integer_factorization

汎用因数分解法は遅いです。ただし、いくつかの特別な目的の方法を使用しようとする場合があります。

于 2012-09-03T16:49:19.883 に答える
0

素数p<=10^9のリストを因数分解数N<=10 ^ 18に格納するというアイデアの問題は、特定のNについては、素数p <= sqrt（N）をループしてチェックする必要があることです。 N％p==0かどうか。これはビジネスを行うための最速の方法ではありません。

10 ^ 18のオーダーの数の束を因数分解したいのか、それともすべての数N <= 10 ^ 18を因数分解したいのかは、質問からは明らかではありません。最初のケースは、因数分解するNの数と、必要な速度に応じて実行可能です。2番目のケースであるN<=10 ^ 18のすべての数値を因数分解することは、10 ^ 18を超える操作（因数分解される数値ごとに少なくとも1つ）を必要とするため、実行できません。コンピューターが1秒あたり10^9のオーダーで実行でき、1年に10 ^ 7秒のオーダーがあることを考えると、長い間ファクタリングすることになります。

10 ^ 18のオーダーの数Nの束を因数分解したいだけの場合、これを行う方法はたくさんあります。「最良の」方法は、特定の番号のプロパティによって異なります。たとえば、10 ^ 18前後のランダムな整数は、10 ^ 9次の2つの素数の積である整数よりも、平均して因数分解するのがはるかに簡単です。これは、より高度なアルゴリズムに移行する前に、試行除算で小さな因数を取り除くことができるためです。これは、プログラミングの質問というよりも、計算数論の質問です。これがあなたの質問であるならば、私はmersenneforum.orgのファクタリングセクションにそれを勧めます。

ばかばかしいほど遅くない迅速で汚い解決策が必要な場合は、車輪の再発明をしないでください。たとえば、GMP-ECMを試すか、PARI/GPで問題を解決できるかどうかを確認してください。

于 2012-09-20T00:59:59.237 に答える