8

为什么此代码返回一个数字的因子之和？

在几个 Project 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 的第 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.

在第二次迭代之后，我们有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）。然后我们只需将它们相乘，就得到了因子的总和。

于 2010-12-17T02:35:41.130 回答
0

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

于 2010-12-17T02:43:21.737 回答