Découverte des tests de primalité⚓︎
Rappels
- Un nombre premier est un entier \(n>1\) qui n'a que deux diviseurs,
- les autres sont dits composés.
- \(1\) n'est ni premier, ni composé.
Dans cette section \(n>1\), sera donc soit premier, soit composé.
n tours de boucle⚓︎
Petit diviseur⚓︎
\(1\) et \(n\) sont toujours des diviseurs de \(n\), ainsi dans \([2 ; n]\) il y en a au moins un.
Écrire une fonction petit_diviseur(n)
dans une console Basthon
qui renvoie le plus petit (hors \(1\)) diviseur de \(n\).
Vérifier
>>> petit_diviseur(2)
2
>>> petit_diviseur(3)
3
>>> petit_diviseur(4)
2
>>> petit_diviseur(5)
5
>>> petit_diviseur(9)
3
Grand diviseur⚓︎
\(1\) et \(n\) sont toujours des diviseurs de \(n\), ainsi dans \([1 ; n-1]\) il y en a au moins un.
Écrire une fonction grand_diviseur(n)
dans une console Basthon
qui renvoie le plus grand (hors \(n\)) diviseur de \(n\).
Vérifier
>>> grand_diviseur(2)
1
>>> grand_diviseur(3)
1
>>> grand_diviseur(4)
2
>>> grand_diviseur(5)
1
>>> grand_diviseur(9)
3
Test de primalité - version 1⚓︎
Écrire une fonction est_premier(n)
qui renvoie un booléen
True
si \(n\) est premier,False
sinon.
Vérifier
>>> est_premier(7)
True
>>> est_premier(25)
False
>>> est_premier(32)
False
>>> est_premier(101)
True
Solution
- On commence une boucle avec \(d = 2\), les diviseurs candidats.
- Tant que \(d < n\),
- on teste si \(d\) est un diviseur
- et on incrémente \(d\) de \(1\), pour passer au suivant.
- On rappelle qu'on travaille ici dans \(\mathbb N^*\),
- on ne traite pas ici le cas \(d=0\).
def est_divible(n, d):
return n % d == 0
def est_premier(n):
"""Renvoie `True` ou `False` selon que
`n` est un nombre premier ou non.
"""
if n < 2:
return False
d = 2
while d < n:
if est_divisible(n, d):
return False
d = d + 1
return True
Tests en pratique⚓︎
- Utiliser ce test de primalité sur les nombres de Mersenne. Jusqu'où allez-vous ?
- Utiliser ce test de primalité sur les nombres de Fermat. Jusqu'où allez-vous ?
- Donner les images
petit_diviseur(F(n))
etpetit_diviseur(M(n))
que vous pouvez trouver.
Factorielle ±1⚓︎
Pour \(n>2\).
- Justifier pourquoi \(n! ±2\) est composé.
- Justifier pourquoi \(n! ±3\) est composé.
- Généraliser !
- Justifier pourquoi Factorielle(n)±1 est un bon candidat pour être premier.
Utiliser votre test de primalité pour trouver des nombres premiers de la forme \(n! ±1\).
√(n) tours de boucle⚓︎
- Justifier que si \(n\) ne possède aucun diviseur \(1<d\leqslant \sqrt{n}\), alors \(n\) est premier.
- Modifier alors votre test de primalité pour le rendre plus efficace.
- Reprendre tous les tests en pratique ! Alors ?
Solution
Il suffit de modifier une ligne
def est_divible(n, d):
return n % d == 0
def est_premier(n):
"""Renvoie `True` ou `False` selon que
`n` est un nombre premier ou non.
"""
if n < 2:
return False
d = 2
while d*d <= n:
if est_divisible(n, d):
return False
d = d + 1
return True