Time complexity of Euler totient function?

Question

To calculate $\phi(n)$, I iterate $k=1$ to $n$ and count how many times $gcd(k,n)=1$.

Would the runtime of the function still be considered $O(n)$? Or would it be $O(n log n)$ due to the gcd?

Answer 1

It would be $O(n\log n)$ due to the time it takes to compute each gcd.

I believe it would be faster to factor $n$ and then use Euler's product formula for $\phi(n)$. Known factoring algorithms are still slow for large numbers $n$, but they do run much faster than $O(n)$. (Even trial division is $O(\sqrt n)$.)