查找因子總和

爲什麼此代碼返回一個數字的因子總和？查找因子總和

在一些項目歐拉問題中，您被要求計算因子的總和作爲問題的一部分。在其中的一個論壇上，有人發佈了以下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

查找因子總和

回答

相關問題