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}$