3

n を表現するための最も単純で時間効率の良いロジックは何でしょうか? 素数の力の産物として？

因数の数を知ることができるように、素数の累乗を見つけることにもっと興味があります。アズン！p1^e1 * p2^e2 * ... * pk^ek のように表すことができます。ここで、各 p は素数であり、n の因数の数は (e1 + 1) (e2 + 1) ... * です。 (ek + 1)

4

1 に答える 1

13

私が知っている素因数分解を見つける最も効率的な方法は、n!各素因数がの素因数として現れる頻度を数えることn!です。明らかに、表示よりも大きいプライムはないnので、プライムにしましょうp <= n。

数字1, ..., nの中には

q1 = floor(n/p)

の倍数p。これらの中には

q2 = floor(q1/p) = floor(n/p²)

の倍数p²。これらの中には

q3 = floor(q2/p) = floor(n/p³)

の倍数p³。などので、pの素因数分解の指数n!は

q1 + q2 + q3 + ...

（a = p^k*bでb割り切れないAnは指数にp寄与し、カウントに対応するリストに表示されます。）そのための関数を簡潔に書くことができます。kkq1, ..., qk

unsigned long long factorial_exponent(unsigned long long n, unsigned long long p) {
    unsigned long long exponent = 0;
    do {
        n /= p;
        exponent += n;
    }while(n);
    return exponent;
}

それはfloor(log n/log p) + 1除算を使用するので、超えない素数nがわかっている場合、それはおよそ貢献します

log n * ∑ (1/log p + 1) ≈ 2n/log n
       p≤n

総作業量への分割と追加。（注：ほとんどの素数≤ nは> √nであり、素数の場合はp > √n明らかにq2 = 0、指数を直接計算する方が高速ですn/p。これにより、必要な除算の数が約半分に減ります。）

超えない素数を見つけるにはn、ふるいを使用するのが最適です。すでに適切な実装がある場合、Sieve of AtkinはO（n）またはO（n / log log n）操作でそれを行います（実装によって異なりますが、実行可能です）範囲はlog log n定数と見なすことができます）、それ以外の場合はエラトステネスのふるいを使用すると、実装が簡単nで、実装に応じて-O（n * log log n）またはO（n）操作を超えない素数を見つけることができます。

そのアルゴリズムの全体的な作業は、素数を見つけることによって支配されます（ただし、実行可能なn場合、指数の決定の寄与は無視できません）。

一方、k ≤ nもちろんそれぞれの素因数分解を見つけるために必要な作業は、それに使用されるアルゴリズムに依存します。そのために試行除算を使用すると、合計で約c*n^1.5/log n-定数を決定するために何もしていませんc。詳細によってはlog n、分子または分母に係数がある場合がありますが、基本的にはn^1.5です。因数分解を見つけるためのより良い方法は、最初にエラトステネスのふるいを変更した最小の素因数[または任意の素因数]をO（n * log log n）演算で見つけ、次にそれを使用して因数分解を見つけることです。 。k因数分解を保存してから、既知の素数除数pで処理するときに、の因数分解を調べることができます。k/p、または、因数分解が完了するまで、などqの既知の素因数を再帰的に検索することにより、その場で因数分解を生成します。これは、既知の素因数が常に最小である場合、処理がはるかに簡単です。k/pk/(p*q)

平均して、の素因数分解には項がk含まれて≈ log log kいるため、メソッドはO（n * log log n）全体の複雑さにつながります。ただし、この方法の定数係数は最初の方法よりもかなり大きいため、素数の検出で同じ複雑さが得られたとしても、最初の方法の方が高速です。

于 2012-05-19T22:32:38.400 に答える