Informations

Auteur(s) Maxime Jacques de Dixmude Slavic
Date limite Pas de date limite
Limite de soumission Pas de limite

Etiquettes

Se connecter

Nombre premier 2

Amé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 parmi 2, 3, . . . , 10. Le gain est appréciable !
  • Cette amélioration est due à la proposition suivante : si un entier n’est pas premier alors il admet un diviseurs d qui vérifie 2 <= d <= racine carre de n.
  • Au lieu de tester si d <= racine carre de n, il est plus facile de tester d² <= n !

Optimisation de est_premier(n)