Activité 10 Nombres premiers
1) Plus petit diviseur.
Programme une fonction plus petit_diviseur(n) qui renvoie, le plus petit
diviseur d 22 de l'entier n > 2
Par exemple plus petit_diviseur(91) renvoie 7. car 91 = 7 x 13.
Méthode.
On rappelle que d divise n si et seulement si n % d vaut 0.
La mauvaise idée est d'utiliser une boucle « pour d variant de 2 à n». En effet
si par exemple on sait que 7 est diviseur de 91 cela ne sert à rien de tester si
8. 9. 10... sont aussi des diviseurs car on a déjà trouvé le plus petit.
• La bonne idée est d'utiliser une boucle « tant que ! Le principe est : « tant
que je n'ai pas obtenu mon diviseur, je continue de chercher ». (Et donc,
dès que je l'ai trouvé, j'arrête de chercher.)
En pratique voici les grandes lignes :
Commence avec d = 2
Tant que d ne divise pas n alors, passe au candidat suivant (d devient d = 1)
À la fin d est le plus petit diviseur de n (dans le pire des cas d = n).
2) Nombres premiers (1).
Modifie la fonction plus petit_diviseur(n) en une fonction est _premier_1(n
qui renvoie « vrai » (True) si n est un nombre premier et « faux » (False) sinon
Par exemple est _premier_1(13) renvoie True, est_premier_1(14) renvoie
False
3) nombres de fermat
Pierre de fermat pensait que tous les entiers Fn = 2puissance 2puissance n + 1 étaient des nombres premiers
Effectivement F0 = 3 F1 = 5 et F2 = 17 sont des nombres premiers
Si il avait connu python il aurait sûrement changé d’avis !
Trouve le plus petit entier Fn qui n’est pas premier
On va améliorer nôtre fonction qui teste si un nombre est premier ou pas cela nous permettra de tester plus vite plein de nombres ou bien des nombres très grands
4) nombres premiers (2)
Ameliore ta fonction en une fonction est_premier_2(n) qui ne teste pas tous les diviseurs d jusqu’à n mais seulement jusqu’à √n
Explication
•par exemple pour tester si 101 est un nombres premiers 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 ≤ √n
•au lieu de tester si d ≤ √n il est plus facile de tester dpuissance 2 ≤ n
5) nombres premiers (3)
Ameliore ta fonction en une fonction est_premier_3(n) à l’aide de l’idée suivante
On teste si d = 2 divise n mais à partir de d=3 il suffit de tester les diviseurs impairs (on teste d puis d+2…)
• par exemple pour tester si n = 419 est un nombre premier on teste d’abord si d = 2 divise n puis d = 3 il suffit de tester les diviseurs impairs (on teste d puis d + 2…)
• par exemple pour tester si n = 419 est un nombre premier on teste d’abord si d = 2 divise n puis d = 3 et ensuite d = 5, d = 7…
•cela permet de faire environ deux fois moins de test !
Explication :
Si un nombre pair d divise par n alors on sait déjà que 2 divise n
Voilà j’espère vrmt que qlq pourras m’aider merci d’avance
Seconde - Sciences Numériques et Technologie - La Programmation en Python
