Time complexity of euler totient function

Question

Code for finding $\phi$(n) is

int phi(int n)
    {    
        int result = n;   // Initialize result as n

        // Consider all prime factors of n and subtract their
        // multiples from result
        for (int p=2; p*p<=n; ++p)
        {
            // Check if p is a prime factor.
            if (n % p == 0)
            {
                // If yes, then update n and result 
                while (n % p == 0)
                    n /= p;
                result -= result / p;
            }
        }

        // If n has a prime factor greater than sqrt(n)
        // (There can be at-most one such prime factor)
        if (n > 1)
            result -= result / n;
        return result;
    }

I don't understand how is the overall complexity $O(\sqrt{n}) $.

From the code, I see that the outer loop runs for $O(\sqrt{n}) $ time but I am not sure of how to include the time complexity of the inner loop for finding the overall complexity.

If we have n=$128$, then outer loop runs for $O(\sqrt{n}) $ time and inner loop for $O(log_2 n)$, so overall complexity is $O(\sqrt{n}) $ + $O(log_2 n)$ which is $O(\sqrt{n}) $.

I don't know how to extend this for general case of $n=P1^{a1}*P2^{a2}*P3^{a3}*..Pn^{an}$

Answer 1

The cost inner loop if $n$ is equal to $P_1^{a_1}P_2^{a_2}\cdots P_k^{a_k}$, should be run in $\log_{P_1}n + \log_{P_2}n + \cdots + \log_{P_k}n$ totaly which is $O(k\log(n))$.Notice that, these computation is computed over the outer loop and summation of all iterations of the outer loop.

To more scrutinizing, as the maximum asymptotic number of primes less than $x$ is $\frac{x}{\log x}$, size of $k$ would be $O(\frac{\sqrt{n}}{\log\sqrt{n}})$. Hence, The complexity of the problem would be: $$O(\sqrt{n} + k\log(n))=O(\sqrt{n} + \frac{\sqrt{n}}{\log\sqrt{n}}\log(n)) = O(\sqrt{n}+\frac{\sqrt{n}}{2})=O(\sqrt{n})$$

Answer 2

Whenever you find a factor, n gets smaller. The amount of work needed to process one factor is trivial compared to the savings you get by dividing n by that factor.