項目歐拉12：與500個因子的三角形數

我正在通過MathBlog上的項目歐拉問題12的解決方案閱讀，我有一些麻煩理解代碼背後的邏輯。該程序使用素數因子分解來查找三角形數的除數。項目歐拉12：與500個因子的三角形數

private int PrimeFactorisationNoD(int number, int[] primelist) { 
    int nod = 1; 
    int exponent; 
    int remain = number; 

    for (int i = 0; i < primelist.Length; i++) { 
     // In case there is a remainder this is a prime factor as well 
     // The exponent of that factor is 1 
     if (**primelist[i] * primelist[i] > number**) { 
      return nod * 2; 
     } 

     exponent = 1; 
     while (remain % primelist[i] == 0) { 
      exponent++; 
      remain = remain/primelist[i]; 
     } 
     nod *= exponent; 

     //If there is no remainder, return the count 
     if (remain == 1) { 
      return nod; 
     } 
    } 
    return nod; 
}

我瞭解程序的大部分內容，除了高亮顯示的部分「primelist [i] * primelist [i]> number」。我無法理解這行代碼的必要性。我將用一個例子來說明我的觀點。假設我有一個數字510 = 2 * 3 * 5 * 17。突出顯示的代碼只有在Primelist編號爲23時才爲真。但是當列表到達編號17時，條件保持== 1將爲真，程序將退出循環。如果我將代碼更改爲if（remaining == primelist [i]）會更好嗎，因爲循環會在primelist變爲17而不是21時結束？

來源

2013-05-18 user2396041

if條件在某些情況下加速了代碼（儘管它應該「保留」而不是「數字」）。一旦達到primelist [i]，我們知道保持不能被primelist [0]通過primelist [i-1]整除。如果primelist [i]^2>仍然存在，那麼我們可以得出結論：primelist [i]和primelist [i]^2-1（含）之間的剩餘是一個素數，就好像剩餘= ab，那麼a，b都必須是至少primelist [我]留下來至少是primelist [i]^2，這是一個矛盾。因此，我們可以停止搜索素數的保留。

對於這個速度更快的例子，取數字= 7。然後，當我們到達3（如3^2 = 9> 7），所以我們並不需要檢查所有的素數高達7

來源

2013-05-18 05:15:14

首先，應該更好地使用條件被觸發remain：

primelist[i] * primelist[i] > remain

這是一個優化，因爲在remain和remain的平方根之間不能有除數，所以您只剩下因子remain。

此外，變量名稱exponent說謊，它確實包含指數加一。更好地將其初始化爲零並乘以exponent + 1。

來源

2013-05-18 07:32:14 starblue

項目歐拉12：與500個因子的三角形數

回答

相關問題