this code solved the problem in under 1 second.

I would say for code that is executed one time ever, even including the sqrt(n) part is premature optimization (though I did include it)