Euler's Sieve for Totient Calculation

Question

這裏的夥計是這個算法，用於找到所有的phi（i）= eulers totient（i） = i < = n。

int phi[n + 1]; 
for (int i = 1; i <= n; ++i) phi[i] = i; 
//invariant: phi(x) for all 1 <= x < d is calculated during the 
//start of the dth iteration. 
for (int d = 1; d <= n; ++d) { //divisors 
    for (int j = 2 * d; j <= n; j += d) phi[j] -= phi[d]; 
} 

如何上面的公式幫助我們實現上面的算法？

Answer 1

從你給的公式開始，如果我們拿島（N）出西格瑪，我們得到：

Sigma[d|n,d!=n]phi(d) + phi(n) = n

因此：

phi(n) = n - Sigma[d|n,d!=n]phi(d)

這是什麼該算法確實：對於每個n，其以n的值開始，並且對於的每個除數d減去除n本身。請注意，這是通過在外部循環中迭代d以及在內部循環中迭代n來以不同的順序完成的，因爲找到數字的倍數比找到它的除數要快。