Euler's product formula

φ (n) = n \prod_{p | n} (1 - \frac{1}{p})

Equivalently,

φ (n) = p_{1}^{k_{1} - 1} (p_{1} - 1) p_{2}^{k_{2} - 1} (p_{2} - 1) \dots p_{r}^{k_{r} - 1} (p_{r} - 1)

where $n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}$ is the prime factorization of $n$ .