φ(n) counts the integers in [1, n] that are coprime to n, meaning their gcd with n is 1.
Counting gcds one by one is O(n log n). Using the prime factorization instead:
φ(n) = n × Π (1 − 1/p) over the distinct primes p dividing n
In integer arithmetic, for each distinct prime factor p, do result -= result / p. Because it reuses the trial-division loop you already wrote, the whole thing runs in O(√n). This is a nice example of how factorization unlocks many other functions.