Formula
φ(n) = n · ∏(1 - 1/p) over distinct primes p dividing n.
Advertisement
Single value
long phi(long n) {
long result = n;
for (long p = 2; p * p <= n; p++) {
if (n % p == 0) {
while (n % p == 0) n /= p;
result -= result / p;
}
}
if (n > 1) result -= result / n;
return result;
}Advertisement
All values ≤ N
Modified sieve: for each prime p, multiply φ[k] by (1 - 1/p) for multiples of p.