Euler's Totient Function — φ(n)

Formula

φ(n) = n · ∏(1 - 1/p) over distinct primes p dividing n.

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;
}

All values ≤ N

Modified sieve: for each prime p, multiply φ[k] by (1 - 1/p) for multiples of p.

Euler's theorem

a^φ(n) ≡ 1 (mod n) if gcd(a, n) = 1. Generalizes Fermat's little theorem.