找到因素之和

Question

为什么此代码返回一个数字的总和？

在一些项目Euler问题中，要求您计算问题的一部分。在其中一个论坛上，有人发布了以下Java代码作为查找总和的最佳方法，因为您实际上不必找到个体因素，只有主要因素（您不需要知道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）的ITH索引：

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

在哪里 m 是独特的主要因素， Ni 是每个唯一因素发生在素数中的次数。

为什么该公式等于因素之和？我的猜测是，它等于通过分布属性的主要因素（即每个唯一因素）的每个唯一组合的总和，但我看不出如何。

Answer 1

让我们看一下最简单的情况： n 是素数的力量。

这些因素 k^m 是1，k，k^2，k^3 ... k^m-1。

现在，让我们看一下算法的内部循环：

第一次迭代后，我们有 k + 1.

在第二次迭代之后，我们有 k(k+1) + 1, ， 或者 k^2 + k + 1

在第三次迭代之后，我们有 k^3 + k^2 + k + 1

等等...

---

这就是它的作用，用于单个素数的数字。我可能会坐下来将其推广到所有数字，但是您可能想先尝试一下。

编辑：既然这是公认的答案，我将通过展示该算法在具有两个不同主要因素的数字上的工作方式来详细说明。然后，将其概括为具有任意数量的不同主要因素的数字是直接的。

这些因素 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的一组因子。