INGIniousAméliore ta fonction en une fonction est_premier_2(n) qui ne teste pas tous les diviseurs d jusqu’à n, mais seulement jusqu’à racine carre de n.
Explications :
- Par exemple, pour tester si 101 est un
nombre premier, il suffit de voir s’il admet des diviseurs parmi2, 3, . . . , 10. Le gain est appréciable ! - Cette amélioration est due à la proposition suivante : si un entier n’est pas
premieralors il admet un diviseursdqui vérifie2 <= d <= racine carre de n. - Au lieu de tester si
d <= racine carre de n, il est plus facile de testerd² <= n!