查找因数和

Question

为什么这段代码会返回一个数字的因数之和？

在几个欧拉计划问题中，你需要计算因数之和作为问题的一部分。在其中一个论坛上，有人发布了以下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子i的第i个索引）：

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

其中m是唯一质因数的数量，Ni是每个唯一质因数在质因数分解中出现的次数。

为什么这个公式等于因子的总和？我的猜测是它通过分配律等于每个唯一的质因数的所有唯一组合（即每个唯一因子），但我不知道如何证明。

- Jake Stevens-Haas

---

我觉得你的意思是 [2*(2*(2+1)+1)+1]=15 - Adrian Petrescu

@Adrian Petrescu：好的，谢谢。我会修复它。 - Jake Stevens-Haas

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也是如此）。然后我们将它们相乘，就得到了我们的因子总和。

- Anon.

---

明白了！如果一个数A=k^mp^n，那么它的因数将是1、k、k^2...k^m、1、p、p^2...p^n以及这两个集合中每个元素的组合。将每个因数作为矩阵中的一个条目，第一行将是1、k、k^2...k^m，第一列将是1、p、p^2...p^n。任何条目ij都将是k^ip^j。补集将是n-i、m-j的条目。第一行将是1、k、k^2...k^m，第二行将是p乘以第一行，第三行将是p^2乘以第一行，最后一行将是p^n乘以第一行。因此，每个条目（即A的每个因数）的总和等于[1+k+k^2+...+k^m]*[1+p+p^2+...+p^n]。再次感谢。 - Jake Stevens-Haas

是的，看起来你理解了 :) - Anon.

Answer 2

该算法基本上是查看n的所有素因子的有序子集合，这类似于n的因子集合。

- perimosocordiae