Crible d'Ératosthène - Python

Crible d’Ératosthène

Soit $n$ un entier supérieur ou égal à $2$.

• On cherche donc tous les nombres premiers inférieurs ou égaux à $n$.

Le principe d’Ératosthène est assez simple, il opère par « élimination ».

• On liste, par ordre croissant, l’ensemble des entiers compris entre $2$ et $n$ ($0$ et $1$ ne sont pas premiers, $2$ est premier).
• On élimine tous les multiples de $2$ (sauf $2$).
• On élimine tous les multiples de $3$ (sauf $3$).
• Et ainsi de suite, en avançant dans la liste mise à jour à chaque fois.
• On s’arrête dès que le diviseur considéré, qui est toujours premier, est strictement supérieur à la racine carrée de $n$, en vertu de la propriété vue en cours :

Propriété

Si un entier naturel $p$ n’admet aucun diviseur premier inférieur ou égal à $\sqrt{p}$, alors $p$ est premier.

• Les nombres restants dans la liste sont tous les nombres premiers inférieurs ou égaux à $n$.

Exemple

Vous retrouverez dans le cours « Nombres premiers et petit théorème de Fermat » un exemple complet avec $n=119$.
Nous allons ici illustrer le cas très simple $n=16$ par un petit tableau, afin de bien comprendre comment aborder l’algorithme Python.

Soit $\purple{\text{L}}$ la liste qui contient en entrée l’ensemble des entiers naturels et contiendra, en sortie, l’ensemble des nombres premiers inférieurs ou égaux à $16$.

• $\sqrt{16}=4$.

Étape $\text i$	$\text L$	$\text{L[i]}$	Multiples de $\text{L[i]}$ ($\text{L[i]}$ excepté)
$\footnotesize 0$	$\scriptsize {\lbrace \red 2,\,3,\,4,\,5,\,6,\,7,\,8,\,9,\,10,\,11,\,12,\,13,\,14,\,15,\,16 \rbrace}$	$\footnotesize {\red 2 < 4}$	$\scriptsize{\lbrace 4,\,6,\,8,\,10,\,12,\,14,\,16 \rbrace}$
$\footnotesize 1$	$\scriptsize {\lbrace 2,\,\red 3,\,5,\,7,\,9,\,11,\,13,\,15 \rbrace}$	$\footnotesize {\red 3 < 4}$	$\scriptsize{\lbrace 9,\,15 \rbrace}$
$\footnotesize 2$	$\scriptsize {\lbrace 2,\,3,\,\red 5,\,7,\,11,\,13 \rbrace}$	$\footnotesize {\red 5 > 4}$

• L’ensemble des nombres premiers inférieurs ou égaux à $16$ est donc :

$$\lbrace 2,\,3,\,5,\,7,\,11,\,13 \rbrace $$

Algorithme Python

• Nous allons avoir besoin de la fontion $\purple{\text{sqrt}}$, que nous importons du module $\purple{\text{math}}$ :

• Nous définissons notre fonction $\purple{\text{crible}}$, qui prendra donc en paramètre un entier $\purple{\text{n}}$ supérieur ou égal à $2$ et qui affichera l’ensemble des nombres premiers inférieurs ou égaux à $\purple{\text{n}}$ :

• Nous initialisons la liste $\purple{\text{L}}$ avec l’ensemble des entiers compris entre $\purple{\text{2}}$ et $\purple{\text{n}}$, par ordre croissant :

Ici, il faut faire attention.
En effet, nous allons parcourir la liste $\purple{\text{L}}$ au moyen d’une boucle $\purple{\text{for}}$, pour vérifier si ses éléments sont des multiples d’un nombre. Et, si c’est le cas, nous supprimerons l’élément, et ce au fur et à mesure.
Or, il faut éviter de « boucler » sur une liste dont on modifie le nombre d’éléments !

• Nous allons donc créer une liste $\purple{\text{P}}$ intermédiaire, et c’est dans cette liste que nous supprimerons les éléments. Puis, au moment adéquat, nous demanderons à ce que $\purple{\text{L}}$ soit égale à $\purple{\text{P}}$.
• Pour l’instant, nous initialisons $\purple{\text{P}}$ avec les mêmes valeurs que $\purple{\text{L}}$ :

Attention

Il ne faut pas écrire : $\purple{\text{P = L}}$ !
Sinon, toute modification dans une liste sera aussi apportée dans l’autre.

• Nous allons chercher les multiples d’un élément de la liste en avançant à chaque fois.
• Nous initialisons donc une variable $\purple{\text{i}}$ avec la valeur $\purple{\text{0}}$.

En effet, initialement, $\purple{\text{L[0]}}=\purple{\text{2}}$, et nous commençons par chercher les multiples de $\purple{\text{2}}$.

• Tant que le nombre dont nous cherchons les multiples, soit $\purple{\text{L[i]}}$, est inférieur ou égal à $\sqrt{\purple{\text{n}}}$, nous continuons d’avancer dans la liste $\purple{\text{L}}$ :

Remarquons au passage que nous avons préféré travailler avec la racine carrée, mais que nous aurions aussi pu considérer la condition : « tant que $(\purple{\text{L[i]}})^2$ est inférieur ou égal à $\purple{\text{n}}$ ».
Nous n’aurions alors pas eu besoin d’importer la fonction $\purple{\text{sqrt}}$.

• Nous allons nous intéresser aux éléments de $\purple{\text{L}}$ qui suivent $\purple{\text{L[i]}}$, au moyen d’une boucle $\purple{\text{for}}$, sans considérer donc $\purple{\text{L[i]}}$ et les éléments qui le précèdent :

• Pour chacun de ces éléments, nous vérifions si c’est un multiple de $\purple{\text{L[i]}}$, c’est-à-dire si le reste de la division euclidienne de $\purple{\text{L[k]}}$ par $\purple{\text{L[i]}}$ est égal à $0$ :

• Si c’est le cas, nous supprimons l’élément de la liste $\purple{\text{P}}$ :

Rappel

L’instruction $\purple{\text{liste.remove(a)}}$ supprime le premier élément de $\purple{\text{liste}}$ égal à $\purple{\text{a}}$.

• La liste $\purple{\text{P}}$ a été créée de façon à ce qu’il n’y ait pas de doublons et, avant suppression, elle contiendra toujours la valeur de $\purple{\text{L[k]}}$. Cette fonction nous convient donc très bien.

• Une fois la boucle $\purple{\text{for}}$ sur $\purple{\text{L}}$ terminée, nous pouvons cette fois y supprimer les multiples trouvés, en nous servant de $\purple{\text{P}}$ :

• Nous allons à l’élément suivant de la liste $\purple{\text{L}}$ :

Nous sortirons de la boucle $\purple{\text{while}}$ dès que $\purple{\text{L[i]}}$ sera strictement supérieur à $\sqrt{\purple{\text{n}}}$.

• $\purple{\text{L}}$ contiendra alors uniquement l’ensemble des nombres premiers inférieurs ou égaux à $\purple{\text{n}}$.
• Nous indiquons d’abord combien il y en a.
• Puis nous affichons leur liste.

À retenir

L’algorithme est terminé :

$\begin{aligned} \textcolor{#A9A9A9}{\text{1}}&\quad\text{from math import sqrt} \\ \textcolor{#A9A9A9}{\text{2}}& \\ \textcolor{#A9A9A9}{\text{3}}&\quad\text{def crible(n):} \\ \textcolor{#A9A9A9}{\text{4}}&\quad\qquad\text{L = [j for j in range(2, n + 1)]} \\ \textcolor{#A9A9A9}{\text{5}}&\quad\qquad\text{P = L[:]} \\ \textcolor{#A9A9A9}{\text{6}}&\quad\qquad\text{i = 0} \\ \textcolor{#A9A9A9}{\text{7}}&\quad\qquad\text{while L[i] <= sqrt(n):} \\ \textcolor{#A9A9A9}{\text{8}}&\quad\qquad\qquad\text{for k in range(i + 1, len(L)):} \\ \textcolor{#A9A9A9}{\text{9}}&\quad\qquad\qquad\qquad\text{if L[k] \% L[i] == 0:} \\ \textcolor{#A9A9A9}{\text{10}}&\quad\qquad\qquad\qquad\qquad\text{P.remove(L[k])} \\ \textcolor{#A9A9A9}{\text{11}}&\quad\qquad\qquad\text{L = P[:]} \\ \textcolor{#A9A9A9}{\text{12}}&\quad\qquad\qquad\text{i = i + 1} \\ \textcolor{#A9A9A9}{\text{13}}&\quad\qquad\text{print($^{\backprime\backprime}$Il y a$^{\prime\prime}$, len(L), $^{\backprime\backprime}$nombres premiers} \\ &\quad\qquad\quad\text{inférieurs ou égaux à$^{\prime\prime}$, n, $^{\backprime\backprime}$:$^{\prime\prime}$)} \\ \textcolor{#A9A9A9}{\text{14}}&\quad\qquad\text{print(L)} \end{aligned}$

Vous pouvez chercher les nombres premiers inférieurs ou égaux à $100$ et vérifier que le programme renvoie bien ce qui est attendu.

Remarquons qu’il existe plusieurs autres façons de programmer en Python le crible d’Ératosthène, pour certaines plus rapides. Mais nous avons ici choisi un programme qui tente d’allier clarté et efficacité.

• Toutefois, bien sûr, si nous entrons un très grand $\purple{\text{n}}$, cela risque de prendre un peu de temps à l’algorithme pour renvoyer la liste des nombres premiers recherchés !

Pour terminer, voici un petit exercice.

• Adapter d’abord le programme $\purple{\text{crible}}$ pour que, au lieu d’afficher le nombre et la liste des nombres premiers inférieurs ou égaux à $\purple{\text{n}}$, il renvoie cette liste.
• Ensuite, s’en servir dans une fonction Python :
• qui prend en paramètres deux entiers naturels $\purple{\text{m}}$ et $\purple{\text{n}}$ tels que $\purple{\text{m}} \leq \purple{\text{n}}$ et $\purple{\text{n}} \geq 2$ ;
• et qui affiche en retour la liste des nombres premiers compris entre $\purple{\text{m}}$ et $\purple{\text{n}}$.