Euler's Totient — Solution & Editorial

Back to the Problem

Factorize N and apply φ(N) = N ∏(1 − 1/p) over its distinct primes — implemented as result -= result / p per prime.

Complexity: O(√N)