來計算整數到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;
}
感謝
很容易說你只需要將'result'初始化爲'M'而不是'n':該函數通過查找'n'的主要因子,並且排除範圍內所有這些因子的倍數。但我並不完全肯定這是正確的,所以不是一個答案。嘗試一下,看看我是多麼的錯誤。 –
謝謝史蒂夫..我已經嘗試過,但它似乎並沒有工作:( – pranay
@SteveJessop雖然提供了一個合理的近似值,但它不完全正確。請參閱http://mathoverflow.net/questions/88777/bound這個計算中的一些邊界的估計相對總值函數 – ffao