Time complexity of euler totient function
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})$$