@icezhou0784 I understand your point.. But I'm wary to assign a complexity of O(nsqrtn) without a proper mathematical proof for why that might be the case. We can't just guess the time complexity. I can see a clear case for O(n^2) fitting as an upper bound, but I do not see one for O(nsqrtn) personally. If someone can provide a proof or explanation for why I'd be very interested to read.

Personally I see your point that we have at most sqrt(N) divisors. But I think we also have to consider the max value of one of those divisors in the sqrt(N) possibilities... And the max value of the divisor can be n. So therefore in that worst case scenario where divisor in n, we are running in O(n^2) and thus that is the time complexity because big O notation takes into account the worst case runtime not average. That is my reasoning behind my position.