How fast is this naive prime factorization algorithm?

I'm looking to figure out the big-o complexity of this code:

prime_factorize(N) {

   for (int i = 2; i <= N; i++) {
       while (N % i == 0) {
           print i
           N = N / i
        }
    }
}

This isn't actually a programming language -- It's just pseudocode.

I know what the pseudocode is doing. It is dividing out all the factors of 2, then 3, etc. I also know that the code can be optimized to only go up to sqrt(N), but I want to figure out the runtime of the code as I posted it.

While it is tempting to say the runtime is quadratic, I am pretty sure that's wrong. The reason why I think it's wrong is because I know that the prime sieve algorithm runs in O(nloglogn) time, and it sort of resembles this algorithm.

Can someone please help me analyze this algorithm?

Solution

It's easy to see that this algorithm runs in O(n) in worst case.

You just need to consider the case where n is a prime number, then i would iterate all the way until N.

The same thing occurs if N is not prime. Take N = 2 * 53 as example. It would take 53 iterations = O(N/2) = O(N).