Thông tin

Tác giả Maxime Jacques de Dixmude Slavic
Hạn chót Không có hạn chót
Giới hạn nộp bài Không có giới hạn

Tags

Đăng nhập

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)