查找因子总和

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

在一些项目欧拉问题中，您被要求计算因子的总和作为问题的一部分。在其中的一个论坛上，有人发布了以下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个指标）：

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

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

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

来源

2010-12-17 Jake Stevens-Haas

我想你的意思是[2 *（2 *（2 + 1）+1）+1] = 15 – 2010-12-17 02:30:35

@Adrian Petrescu：是的，谢谢。我会修复它 – 2010-12-17 02:35:59

我们来看最简单的情况：当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-17 02:35:41

谢谢，我会试一试。 1秒。 – 2010-12-17 02:40:09

Got it！如果数字A = k^m * p^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^i * p^j。补充将是入口n-i，m-j。第一行是1，k，k^2 ... k^m，第二行是px第一行，第三行是p^2 x第一行，最后一行是p^nx第一排。因此，每个条目的总和（即A的每个因子）等于[1 + k + k^2 + ... + k^m] * [1 + p + p^2 + ... + p^N]。再次感谢 – 2010-12-17 02:58:35

是的，好像你明白了:) – 2010-12-17 03:03:35

该算法实质上是查看n的素因子的所有有序子集的集合，这与n的因子集合类似。

来源

2010-12-17 02:43:21 perimosocordiae

查找因子总和

回答

相关问题