2

別の数値 (m など) よりも小さくない数値 (n など) の約数を見つける効率的な方法はありますか。n は 10^12 までです。ふるいアルゴリズムについて考えてから、除数の数を見つけました。私の方法は、m から n の平方根までのすべての数値をチェックします。しかし、それを行う別の（効率的な）方法があると思います。

4

3 に答える 3

3

素因数がわかっている場合、数値の約数を見つけるのは簡単です。すべての要因の多重度のすべての可能な組み合わせを取るだけです。

nが 10^12 と小さい場合、10^6 までの潜在的な要因をチェックするだけでよいため、試行分割は十分に高速な因数分解方法である必要があります。

編集：「すべての可能な組み合わせ」と試行分割による因数分解に関する議論を追加します。

数 24505 = 5 * 13 * 13 * 29 を考えてみましょう。その約数を列挙するには、すべての因数の多重度のすべての可能な組み合わせを取ります。

5^0 * 13^0 * 29^0 = 1
5^0 * 13^0 * 29^1 = 29
5^0 * 13^1 * 29^0 = 13
5^0 * 13^1 * 29^1 = 377
5^0 * 13^2 * 29^0 = 169
5^0 * 13^2 * 29^1 = 4901
5^1 * 13^0 * 29^0 = 5
5^1 * 13^0 * 29^1 = 145
5^1 * 13^1 * 29^0 = 65
5^1 * 13^1 * 29^1 = 1885
5^1 * 13^2 * 29^0 = 845
5^1 * 13^2 * 29^1 = 24505

試行分割による数の素因数分解も難しくありません。これがアルゴリズムです。これをお気に入りの言語に翻訳できます。10 ^ 12 までの数値に対しては十分に高速です。

function factors(n)
    f = 2
    while f * f <= n
        if n % f == 0
            output f
            n = n / f
        else
            f = f + 1
    output n

24505 の素因数分解を見てみましょう。最初はfは 2 ですが、24505 % 2 = 1 なので、fは 3 にインクリメントされます。次に、f = 3 とf = 4 もnの除算に失敗しますが、24505 % 5 = 0 なので 5は 24505 の因数であり、nは 24505 / 5 = 4901 に減少します。現在、 f = 5 は変更されていませんが、6、7、8、9、10、11、12 と同様にnの除算に失敗しますが、最終的には 4901 % 13 になります。 = 0 であるため、13 は 4901 (および 24505) の係数であり、nは 4901 / 13 = 377 に減らされます。この時点でf = 13 は変更されず、13 は再び除数になります。今回は減らされたn = 377 なので、13 の別の因数が出力され、nは 29 に減らされます。この時点で 13 * 13 = 169 は 29 より大きいため、whileループが終了し、29 の最終係数が出力されます。これが機能するのは、 n=pqの場合、pまたはqのいずれかがnの平方根よりも小さくなければならないためです( pとqが等しく、nが完全平方の場合を除く)。 29 の平方根よりも小さいすべてのpとqによって、それは素数でなければならず、したがって最終因数です。したがって、24505 = 5 * 13 * 13 * 29 であることがわかります。

これらの種類のアルゴリズムについては、エッセイ Programming with Prime Numbersで説明しています。

于 2012-10-30T19:31:33.683 に答える
2

以下は、m より大きい n の約数を計算するプログラムの例です。c 個の除数がある場合、largeDivs() コードは時間 O(c) で実行されます。largeDivs() も因数分解された数としての n の表現で始まります。nset は、n = Product{p_i**k_i for i in 1..h} となる形式 (p_i, k_i) のペアのリストです。プログラムの後に、いくつかの出力例を示します。check() ルーチンは、largeDivs() が正しい結果を生成することを示すために使用されます。m の値が小さいと、check() に時間がかかります。

def largeDivs(n, nset, m):
    p, k = nset[-1]
    dd = 0
    if len(nset) > 1:
        nn, mm = n / p**k, m
        for i in range(k+1):
            dd += largeDivs(nn, nset[:-1], mm)
            mm = (mm + p-1)/p
    else:
        c, v = k+1, 1
        while v<m and c>0:
            c, v = c-1, v*p
        return c
    return dd

def check (n,m,s):
    if m<1:
        return s
    c = 0
    for i in range(m,n+1):
        if (n%i)==0:
            c += 1
    return c


tset = [(2,3),(3,2),(11,1),(17,1),(23,2)]
n = s = 1
for i in tset:
    s *= 1+i[1]
    n *= i[0]**i[1]
print 'n=',n, '  s=',s
m=0
for i in range(8):
    print 'm:', m, '\t', largeDivs(n, tset, m), '  Check:',check(n,m,s)
    m = 10*m + 5

出力例:

n= 7122456   s= 144
m: 0    144   Check: 144
m: 5    140   Check: 140
m: 55   124   Check: 124
m: 555  95   Check: 95
m: 5555     61   Check: 61
m: 55555    28   Check: 28
m: 555555   9   Check: 9
m: 5555555  1   Check: 1
于 2012-10-30T23:32:10.203 に答える
0

アプリケーションにもよりますが、パフォーマンスがそのような問題である場合は、事前に生成されたハッシュ テーブルを使用します。明らかに、10^12 エントリをメモリに格納するのは非現実的 (または少なくとも望ましくない) かもしれないので、k番目の素数まで除算テストを行い、最初のk 個の素数で割り切れない数に対してのみハッシュ テーブル エントリを生成します。

たとえば、大まかに書かれていてテストされていませんが、これはアイデアを与えるはずです:

int   number   = 23456789;
int   primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 0};
int   pfactors = 0;
int*  prime = primes;
float temp;

// check until we reach the end of the array (0)
while (prime)
{
    // divide by prime and check if result is integer
    temp = (float)number/*prime;
    if (temp == floor(temp))
    {
        // if so, increment count of prime factors and loop (same prime again!)
        pfactors++;
        number = (int)temp;
    }
    else
    {
        // else try the next prime
        prime++;
    }
}

// finally, rely on hash table magic
pfactors += pregenerated_hash[number];
于 2012-10-30T19:54:24.383 に答える