8

このコードが数値の因数の合計を返すのはなぜですか?

いくつかの Project Euler の問題では、問題の一部として因数の合計を計算するよう求められます。そこのフォーラムの 1 つで、誰かが次の Java コードをその合計を見つける最善の方法として投稿しました。以下の私の要約にスキップできます）：

public int sumOfDivisors(int n)
{
    int prod=1;
    for(int k=2;k*k<=n;k++){
        int p=1;
        while(n%k==0){
            p=p*k+1;
            n/=k;
        }
        prod*=p;
    }
    if(n>1)
        prod*=1+n;
    return prod;
}

今、何度も試してみましたが、うまくいくことがわかりました。問題は、なぜですか？

因数100: とし1,2,4,5,10,20,25,50,100ます。合計は217です。素因数分解は2*2*5*5です。この関数はあなたに[5*(5+1)+1]*[2*(2+1)+1] = [25+5+1]*[4+2+1] = 217

ファクタリング8: 1,2,4,8. 合計は15です。素因数分解は2*2*2です。この関数はあなたに[2*(2*(2+1)+1)+1]=15

アルゴリズムは次のように要約されます (Fi因子 F または F sub i の i 番目のインデックスを意味するために使用):

return product(sum(Fi^k, k from 0 to Ni), i from 1 to m)

ここで、mは一意の素因数の数、Niは素因数分解で各一意の要素が発生する回数です。

この式が因数の合計に等しいのはなぜですか? 私の推測では、分配特性を介して素因数のすべての一意の組み合わせ (つまり、すべての一意の要素) の合計に等しいと思いますが、その方法はわかりません。

4

2 に答える 2

7

最も単純なケースを見てみましょう: nが素数の累乗の場合です。

の因数k^mは 1、k、k^2、k^3 ... k^m-1 です。

次に、アルゴリズムの内側のループを見てみましょう。

最初の反復の後、 が得られk + 1ます。

2 回目の反復の後k(k+1) + 1、またはk^2 + k + 1

3回目の繰り返しの後、k^3 + k^2 + k + 1

等々...

これが、単一の素数の累乗である数値に対して機能する方法です。座ってこれをすべての数値に一般化するかもしれませんが、最初に自分で試してみることをお勧めします.

編集:これが受け入れられた答えになったので、アルゴリズムが2つの異なる素因数を持つ数値でどのように機能するかを示すことで、もう少し詳しく説明します。それを任意の量の異なる素因数を持つ数に一般化するのは簡単です。

の因数x^i.y^jはx^0.y^0、x^0.y^1... x^0.y^j、x^1.y^0...

異なる素因数ごとに内側のループが生成されますx^i + x^i-1 + ... + x^0(および同様に も生成されyます)。次に、それらを掛け合わせるだけで、因数の合計が得られます。

于 2010-12-17T02:35:41.130 に答える
0

このアルゴリズムは基本的に、n の因数の集合に類似した、n の素因数のすべての順序付けられたサブセットの集合を調べています。

于 2010-12-17T02:43:21.737 に答える