Comment l'intérêt entier n'est-il pas dans $ p $?

Question

Tout le monde ne cesse de prétendre que le fait entier est dans $ np $ mais je ne comprends tout simplement pas ... même avec l'algorithme le plus simple (division avec tous les entiers jusqu'à $ sqrt {n} $) La complexité devrait être $ sqrt { n} log (n) $ ... comment n'est-ce pas dans $ p $? Y a-t-il quelque chose qui me manque?