How do you compute Euler's phi function using the prime factorization formula?

Question

Accepted Answer

$\varphi(n) = n \cdot \prod_{p|n}\left(1 - \frac{1}{p}\right)$ — multiply n by $(1 - 1/p)$ for each distinct prime factor p of n.
The formula: For $n = p_1^{a_1} \cdot p_2^{a_2} \cdot ... \cdot p_k^{a_k}$:
$$\varphi(n) = n \cdot \prod_{p|n}\left(1 - \frac{1}{p}\right) = n \cdot \frac{p_1-1}{p_1} \cdot \frac{p_2-1}{p_2} \cdot ... \cdot \frac{p_k-1}{p_k}$$
Example: $\varphi(315)$

$315 = 3^2 \cdot 5 \cdot 7$ (prime factors: 3, 5, 7)
$\varphi(315) = 315 \cdot \frac{2}{3} \cdot \frac{4}{5} \cdot \frac{6}{7} = 315 \cdot \frac{2}{3} \cdot \frac{4}{5} \cdot \frac{6}{7} = 144$

Example: $\varphi(40)$

$40 = 2^3 \cdot 5$ (prime factors: 2, 5)
$\varphi(40) = 40 \cdot \frac{1}{2} \cdot \frac{4}{5} = 16$

Why this is powerful: You don't need to factorize into individual prime powers and apply rules 1-3 separately. One formula handles everything, as long as you know the prime factors.
Tip: This formula only uses the distinct prime factors, not their exponents directly. Whether a prime appears once or five times, it contributes the same $(1 - 1/p)$ factor — the exponent's effect is already captured by the leading $n$.
Go deeper:

Euler's totient function (Wikipedia) — the product formula over distinct prime factors.