計算歐拉披功能

int phi (int n) { 
    int result = n; 
    for (int i=2; i*i<=n; ++i) 
     if (n % i == 0) { 
      while (n % i == 0) 
       n /= i; 
      result -= result/i; 
     } 
    if (n > 1) 
     result -= result/n; 
    return result; 
}

我看到上面的實現歐拉披功能這是的O（開方N）。我不明白在for循環，需要使用i*i<=n的事實的變化n。據說它可以在更小的時間內完成O（sqrt n）如何？ link (in Russian)計算歐拉披功能

來源

2015-06-05 DCoder

i*i<=n與i<= sqrt(n)相同，從中您的迭代僅持續到sqrt(n)的順序。

使用Euler totient function的直接定義，應該找到除n的素數。

來源

2015-06-05 13:48:00

這個函數是通過試驗除法對整數因子分解的直接實現，只是它不是報告找到它們的因素，而是使用因子來計算phi。通過使用更好的算法找出因子，phi的計算可以在小於O（sqrt n）的時間內完成;要做到這一點的最佳方式取決於的大小，即。

來源

2015-06-05 15:35:02 user448810

什麼意思是更好的算法找到的因素？.Plz提到的算法的名稱 – DCoder

ρ和p-1算法，SQUFOF，連續分數，橢圓曲線算法，二次篩，數字場篩和許多其他現在不會想到。請注意，其中一些只能在專家手中運行良好。 – user448810

@DCoder爲什麼不按照剛剛引用的頁面上的鏈接，它說你可以找到phi「比O（sqrt（n））更快？」該鏈接回答了這個問題，這不應該是一個驚喜，因爲它還提到「有效的保理算法」。它描述了像Pollard rho因子分解這樣的事情，它可以跳過20位以上的數字。我不明白你如何閱讀該頁面，而不願意遵循它的鏈接。 –

如果您希望總數的最大數（N表示）足夠小以至於您可以在內存中放置一個大小爲N的表格，那麼您可以在每次評估時做得更好，代價是有在任何評估之前建立一個表格。

一種方法是首先建立一個素數表，然後用至多sqrt（n）的每個整數進行試劃分，然後用sqrt（n）中的每個素數進行試劃分。

你可以通過建立一個表格來代替素數表格，這個表格給出了（對於每個整數2..N）分割數字的最小素數。可以使用通常的Sieve of Eratosthenes的簡單修改來構建這樣的表格。然後爲了計算一個數字的總數，你使用表格來找出除數字以外的最小的素數（並將其累積到你的答案中），然後用表格條目除數，使用表格找出除以這個數字的最小素數，等等。

來源

2015-06-05 16:54:52 dmuir

計算歐拉披功能

回答

相關問題