Crible d'Ératosthène
Nombres premiers
- \(0\) et \(1\) ne sont pas des nombres premiers, par définition.
- Pour un entier \(n>1\), on dit que \(n\) est nombre premier s'il ne possède que deux diviseurs entiers \(1\) et \(n\).
Par exemple :
- \(2\) est premier ; \(1×2\) est le seul produit d'entier égal à \(2\).
- \(3\) est premier ; \(1×3\) est le seul produit d'entier égal à \(3\).
- \(4\) n'est pas premier ; il est aussi multiple de \(2\), avec \(2×2 = 4\).
- \(5\) est premier ; \(1×5\) est le seul produit d'entier égal à \(5\).
Propriété importante : un entier \(n>1\) est toujours multiple d'un nombre premier, parfois lui-même uniquement. C'est cette propriété que nous allons utiliser pour justifier le fonctionnement du crible d'Ératosthène.
On va marquer les multiples des nombres premiers, le plus petit entier non marqué sera donc un nombre premier.
Le crible d'Ératosthène
Un crible est une technique qui permet de répondre sur les caractéristiques d'entiers, non pas un à la fois, mais sur plusieurs à la fois. Il existe des cribles pour autre chose que les nombres premiers.
Le crible d'Ératosthène permet de déterminer les nombres premiers jusqu'à un certain nombre \(n\) fixé. La démarche avec un papier et un crayon est la suivante :
- On écrit tous les entiers jusqu'à \(n\).
- On raye \(0\) et \(1\) qui ne sont pas premiers.
- On répète jusqu'à avoir traité tous les nombres :
- Le prochain nombre non traité est un nombre premier ; on l'entoure.
- On raye tous les autres multiples de ce nombre.
Avec Python, si l'on cherche les nombres premiers jusqu'à n :
- On construit un tableau de \(n+1\) booléens
crible, initialement tous égaux àTrue. - On modifie
crible[0]etcrible[1]àFalse; \(0\) et \(1\) ne sont pas premiers. Pour \(1\), il faut vérifier avant que \(n>0\). - On parcourt ce tableau de gauche à droite. Pour chaque indice
p:- Si
crible[p]vautTrue: le nombre \(p\) est premier.- On donne la valeur
Falseà toutes les cellules decribledont l'indice est un multiple dep, on commence avec2*p, puis3*petc jusqu'à la fin du tableau.
- On donne la valeur
- Sinon,
crible[p]vautFalse: le nombre \(p\) n'est pas premier. On n'effectue aucun changement sur le tableau.
- Si
Utilisation : On peut établir ensuite la liste des nombres premiers jusqu'à \(n\) en filtrant les indices des cellules de crible valant True.
Astuce
L'expression Python range(2*p, n + 1, p) permet d'itérer sur tous les multiples de p, de 2*p inclus à n inclus.
Compléter la fonction eratosthene :
- prenant en paramètre un entier
npositif, - renvoyant le tableau
criblede taille \(n+1\) contenant des booléens,crible[p]indique sipest premier.
Compléter la fonction premiers_jusque :
- prenant en paramètre un entier
npositif, - renvoyant la liste des nombres premiers jusqu'à \(n\).
Exemples
>>> eratosthene(5)
[False, False, True, True, False, True]
>>> eratosthene(6)
[False, False, True, True, False, True, False]
>>> premiers_jusque(5)
[2, 3, 5]
>>> premiers_jusque(6)
[2, 3, 5]
>>> premiers_jusque(20)
[2, 3, 5, 7, 11, 13, 17, 19]
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)