I am trying to understand the time complexity of the following solution to finding the largest prime factor of a positive integer.
https://www.geeksforgeeks.org/find-largest-prime-factor-number/
Let's suppose a number is already prime, say $N = 6247$. According to the algorithm we loop at most $\sqrt(N)$ times looking for a prime to divide out. However, in cases where $N$ is not prime, we have an inner while loop that divides out all occurrences of a given prime. How can we prove that the inner loop doesn't increase the asymptotic complexity of the algorithm?
More rigorously, if $N = p_{1}^{a_{1}} p_{2}^{a_{2}}...p_{n}^{a_{n}},$ prove that $\sum_{i=1}^{n}a_{i} = O(\sqrt(N)).$
The last estimate in your question follows, in a much stronger form, by simply taking the logarithm. Namely, let $N = p_1^{a_1}p_2^{a_2} ... p_n^{a_n}$, where $2\leq p_1<p_2<...<p_n$. Then applying $\log$ on both sides we get $$ \log N = a_1 \log p_1 + ...+a_n \log p_n \geq (a_1+...+a_n) \log p_1 \geq (a_1+...+a_n) \log 2. $$ Hence, $$ \sum\limits_{i=1}^n a_i \leq \frac{\log N}{\log 2}, $$ which is a much stronger upper bound than $\sqrt{N}$.