CP-Snippets

totient-seive

• totient-seive

• https://thesobersobber.github.io/CP-Snippets/totient-seive
  

• github-snip-file

  for (int i = 1; i < MN; i++)
    phi[i] = i;

  for (int i = 1; i < MN; i++)
    if (!sieve[i]) // is prime
      for (int j = i; j < MN; j += i)
        phi[j] -= phi[j] / i;