找出因素的总和

Question

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

在几个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的数量是每个唯一因子在素数因子分解中出现的次数.

为什么这个公式等于因子的总和？我的猜测是,它等于通过分配属性的每个独特的素因子组合(即每个独特因子)的总和,但我不知道如何.

Answer 1

让我们看一下最简单的情况:当n是素数的幂时.

因子为k^m1,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).然后我们将它们相乘,我们得到了各种因素.