Crible d'Ératosthène (1)
Le cadre
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.
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 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.
Algorithme décrit pour Python
Avec Python, pour chercher les nombres premiers jusqu'à n inclus :
- On construit un tableau de
n + 1booléenscrible, 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 quen > 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 * p, etc, jusqu'à la fin du tableau.
- On donne la valeur
- Sinon,
crible[p]vautFalse: le nombrepn'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.
Exercice
Coder une fonction ératosthène :
- qui prend en paramètre un entier naturel
n, - et qui renvoie le tableau
criblede taillen + 1contenant des booléens,crible[p]indique sipest premier.
Coder une fonction premiers_jusque :
- qui prend en paramètre un entier naturel
n, - et qui renvoie la liste des nombres premiers jusqu'à \(n\) inclus.
Exemples
>>> ératosthène(5)
[False, False, True, True, False, True]
>>> ératosthène(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)