[gsliepen]

You are assuming division itself is an O(1) operation. However, it also scales with the size of the number. So more correct would be to say that this naive method is O(sqrt(N) log(N) log(log(N))).

[xpe]

I was both hoping and fearing that someone would correct my simplification. (That is more nested logs than I would’ve guessed however.)