Médaille
N°1 pour apprendre & réviser du collège au lycée.
Crible d'Ératosthène - Python
Fiche méthode

Introduction :

Le crible d’Ératosthène, savant grec du IIIe siècle avant J.-C., permet de déterminer l’ensemble des nombres premiers inférieurs ou égaux à un entier naturel nn donné.
Dans cette fiche, et plus de vingt siècles après, nous allons voir comment nous pouvons programmer informatiquement, en Python, l’algorithme qu’il a imaginé.

Crible d’Ératosthène

Soit nn un entier supérieur ou égal à 22.

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

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

  • On liste, par ordre croissant, l’ensemble des entiers compris entre 22 et nn (00 et 11 ne sont pas premiers, 22 est premier).
  • On élimine tous les multiples de 22 (sauf 22).
  • On élimine tous les multiples de 33 (sauf 33).
  • 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 nn, en vertu de la propriété vue en cours :
bannière propriete

Propriété

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

  • Les nombres restants dans la liste sont tous les nombres premiers inférieurs ou égaux à nn.
bannière exemple

Exemple

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

Soit L\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 à 1616.

  • 16=4\sqrt{16}=4.

Étape i\text i L\text L L[i]\text{L[i]} Multiples de L[i]\text{L[i]}

(L[i]\text{L[i]} excepté)

0\footnotesize 0 {2,3,4,5,6,7,8,9,10,11,12,13,¨C20C14,¨C21C15,¨C22C16}\scriptsize {\lbrace \red 2,\,3,\,4,\,5,\,6,\,7,\,8,\,9,\,10,\,11,\,12,\,13,\,14,\,15,\,16 \rbrace} 2<4\footnotesize {\red 2 < 4} {4,¨C23C6,¨C24C8,¨C25C10,¨C26C12,¨C27C14,¨C28C16}\scriptsize{\lbrace 4,\,6,\,8,\,10,\,12,\,14,\,16 \rbrace}
1\footnotesize 1 {2,3,5,7,9,11,13,15}\scriptsize {\lbrace 2,\,\red 3,\,5,\,7,\,9,\,11,\,13,\,15 \rbrace} 3<4\footnotesize {\red 3 < 4} {9,15}\scriptsize{\lbrace 9,\,15 \rbrace}
2\footnotesize 2 {2,3,5,7,11,13}\scriptsize {\lbrace 2,\,3,\,\red 5,\,7,\,11,\,13 \rbrace} 5>4\footnotesize {\red 5 > 4}
  • L’ensemble des nombres premiers inférieurs ou égaux à 1616 est donc :

{2,3,5,7,11,13}\lbrace 2,\,3,\,5,\,7,\,11,\,13 \rbrace

Algorithme Python

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

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

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

L = [j for j in range(2, n + 1)]\text{L = [j for j in range(2, n + 1)]}

Ici, il faut faire attention.
En effet, nous allons parcourir la liste L\purple{\text{L}} au moyen d’une boucle for\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 P\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 L\purple{\text{L}} soit égale à P\purple{\text{P}}.
  • Pour l’instant, nous initialisons P\purple{\text{P}} avec les mêmes valeurs que L\purple{\text{L}} :

P = L[:]\text{P = L[:]}
bannière attention

Attention

Il ne faut pas écrire : P = L\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 i\purple{\text{i}} avec la valeur 0\purple{\text{0}}.

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

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

while L[i] <= sqrt(n):\text{while L[i] <= sqrt(n):}

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 (L[i])2(\purple{\text{L[i]}})^2 est inférieur ou égal à n\purple{\text{n}} ».
Nous n’aurions alors pas eu besoin d’importer la fonction sqrt\purple{\text{sqrt}}.

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

for k in range(i + 1, len(L)):\text{for k in range(i + 1, len(L)):}
  • Pour chacun de ces éléments, nous vérifions si c’est un multiple de L[i]\purple{\text{L[i]}}, c’est-à-dire si le reste de la division euclidienne de L[k]\purple{\text{L[k]}} par L[i]\purple{\text{L[i]}} est égal à 00 :

if L[k] % L[i] == 0:\text{if L[k] \% L[i] == 0:}
  • Si c’est le cas, nous supprimons l’élément de la liste P\purple{\text{P}} :

P.remove(L[k])\text{P.remove(L[k])}
bannière rappel

Rappel

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

  • La liste P\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 L[k]\purple{\text{L[k]}}. Cette fonction nous convient donc très bien.
  • Une fois la boucle for\purple{\text{for}} sur L\purple{\text{L}} terminée, nous pouvons cette fois y supprimer les multiples trouvés, en nous servant de P\purple{\text{P}} :

L = P[:]\text{L = P[:]}
  • Nous allons à l’élément suivant de la liste L\purple{\text{L}} :

i = i + 1\text{i = i + 1}

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

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

print(Il y a, len(L), nombres premiers infeˊrieurs ou eˊgaux aˋ, n, :)print(L)\begin{aligned} &\text{print($^{\backprime\backprime}$Il y a$^{\prime\prime}$, len(L), $^{\backprime\backprime}$nombres premiers inférieurs ou égaux à$^{\prime\prime}$, n, $^{\backprime\backprime}$:$^{\prime\prime}$)} \ &\text{print(L)} \end{aligned}
bannière à retenir

À retenir

L’algorithme est terminé :

1from math import sqrt23def crible(n):4L = [j for j in range(2, n + 1)]5P = L[:]6i = 07while L[i] <= sqrt(n):822¨C12Cfor k in range(i + 1, len(L)):9¨C13C¨C14C¨C15C¨C16Cif L[k] % L[i] == 0:10¨C17C¨C18C¨C19C¨C20C¨C21CP.remove(L[k])11¨C22C¨C23C¨C24CL = P[:]12¨C25C¨C26C¨C27Ci = i + 113¨C28C¨C29Cprint(Il y a, len(L), nombres premiers¨C30C¨C31C¨C32Cinfeˊrieurs ou eˊgaux aˋ, n, :)14¨C33C¨C34Cprint(L)\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 à 100100 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 n\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 crible\purple{\text{crible}} pour que, au lieu d’afficher le nombre et la liste des nombres premiers inférieurs ou égaux à n\purple{\text{n}}, il renvoie cette liste.
  • Ensuite, s’en servir dans une fonction Python :
  • qui prend en paramètres deux entiers naturels m\purple{\text{m}} et n\purple{\text{n}} tels que mn\purple{\text{m}} \leq \purple{\text{n}} et n2\purple{\text{n}} \geq 2 ;
  • et qui affiche en retour la liste des nombres premiers compris entre m\purple{\text{m}} et n\purple{\text{n}}.