In che modo il factoring intero non è in $ p $?

Question

Tutti continuano a sostenere che il factoring intero è in $ np $ ma non lo capisco ... anche con l'algoritmo più semplice (divisione con tutti i numeri interi fino a $ sqrt {n} $) la complessità dovrebbe essere $ sqrt { n} log (n) $ ... come non va in $ p $? C'è qualcosa che mi manca?