ファクタの合計を求める

Question

なぜこのコードは数値の合計を返しますか？

Project Eulerのいくつかの問題では、問題の一部として要因の合計を計算するよう求められます。フォーラムの1つで、誰かが個々の要素を見つけ出す必要はほとんどなく、重要なものだけを見つける必要がないので、誰かがその合計を見つける最良の方法として次のJavaコードを投稿しました（Javaを知る必要はなく、私の要約にスキップすることができます）：

今、私は何度も試してみましたが、それは動作することがわかりました。問題は、なぜですか？

あなたには、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です。

mはユニークな素因数の数である

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

、Niがある：この関数は、アルゴリズムが（因子FまたはFサブIのi番目のインデックスを意味するFiを使用して）に帰着あなた[2*(2*(2+1)+1)+1]=15

を与えます各素因数が素因数分解で発生する回数。

なぜこの式は要因の合計に等しいのですか？私の推測では、それは分布プロパティによるプライムファクタのすべての固有の組み合わせ（つまり、すべての固有のファクタ）の合計に等しいですが、どのように見えません。

Answer 1

最も単純なケースを見てみましょう。nは素数の冪乗です。

ファクタは、1、k、k^2、k^3 ... k^m-1です。

今度は、アルゴリズムの内部ループを見てみましょう：

最初の繰り返しの後、我々はk + 1を持っています。

2回目の繰り返しの後、我々は3回目の反復後k(k+1) + 1、またはk^2 + k + 1

を持って、我々はk^3 + k^2 + k + 1

を持っているように...

---

それは数字のためにどのように動作するかですそれは単一の素数のべき乗です。私は座って、これをすべての数字に一般化するかもしれませんが、あなたはそれを最初に自分自身に与えたいかもしれません。

EDIT：これが受け入れられた答えであるので、アルゴリズムが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）を生成します。それから、それらを掛け合わせるだけで、我々は要素の合計を持っています。

Answer 2

アルゴリズムは基本的に、nの因子の集合に類似したnの素因数のすべての順序付き部分集合の集合を調べています。