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