Totient sieve

A totient sieve computes the Euler totient function for many integers at once. Initialize $\varphi (n)=n$ and, for each prime $p$, replace $\varphi (n)$ by $\varphi (n)(1-1/p)$ for every multiple $n$ of $p$.