修改Euler Totient函數

來計算整數到N和小於N的整數我們可以簡單地計算它的ETF。但是要計算共素數爲N但小於M的整數數目，那麼我們如何修改/計算它呢？我已經嘗試過計算ETF的代碼，但無法繼續如何修改它以獲得所需的結果。修改Euler Totient函數

代碼：

int etf(int n) 
{ 
    int result = n; 
    int i; 
    for(i=2;i*i <= n;i++) 
    { 

     if (n % i == 0) result -= result/i; 
     while (n % i == 0) n /= i; 
    } 
    if (n > 1) result -= result/n; 
    return result; 
}

感謝

來源

2012-10-03 pranay

很容易說你只需要將'result'初始化爲'M'而不是'n'：該函數通過查找'n'的主要因子，並且排除範圍內所有這些因子的倍數。但我並不完全肯定這是正確的，所以不是一個答案。嘗試一下，看看我是多麼的錯誤。 –

謝謝史蒂夫..我已經嘗試過，但它似乎並沒有工作:( – pranay

@SteveJessop雖然提供了一個合理的近似值，但它不完全正確。請參閱http://mathoverflow.net/questions/88777/bound這個計算中的一些邊界的估計相對總值函數 – ffao

您需要使用inclusion-exclusion principle。讓我們來舉個例子：假設你想計算整數副本數爲30 = 2 * 3 * 5且小於20.

首先要注意的是，你可以計算非互質數爲30並從總數中減去它們，這是更容易。小於20的2的倍數是20/2 = 10，3的倍數是20/3 = 6（取底板），5的倍數是20/5 = 4。

但是，請注意，我們不止一次地計算了諸如6 = 2 * 3的數字，都是2的倍數和3的倍數。爲了說明這一點，我們必須減去作爲乘積的倍數的每個數字兩個素數。

另一方面，這又會減去三次素數的倍數的數字 - 因此您必須將該次數加到最後。這樣做，交替的跡象，直到你達到除N的素數總數。在這個例子中，答案將是

20/1 - 20/2 - 20/3 - 20/5 + 20/2 * 3 + 20/3 * 5 + 20/2 * 5-20/2 * 3 * 5 = 20 - 10 - 6 - 4 + 3 + 1 + 2 - 0 = 6.

我們計算的數字是1,7,11,13,17和19.）

來源

2012-10-03 18:33:36 ffao

非常感謝ffao，但我無法得到如何對它進行編碼，我的意思是我有多少次循環，例如（i = 0; i pranay

循環遍歷所有子集et是一個典型的問題 - 你肯定不想要「n for循環」。您可以迭代位掩碼或遞歸執行。 – ffao

非常感謝ffao :) – pranay

修改Euler Totient函數

回答

相關問題