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 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
Crible d’Ératosthène
Soit un entier supérieur ou égal à .
- On cherche donc tous les nombres premiers inférieurs ou égaux à .
Le principe d’Ératosthène est assez simple, il opère par « élimination ».
- On liste, par ordre croissant, l’ensemble des entiers compris entre et ( et ne sont pas premiers, est premier).
- On élimine tous les multiples de (sauf ).
- On élimine tous les multiples de (sauf ).
- 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 , en vertu de la propriété vue en cours :
Si un entier naturel n’admet aucun diviseur premier inférieur ou égal à , alors est premier.
- Les nombres restants dans la liste sont tous les nombres premiers inférieurs ou égaux à .
Vous retrouverez dans le cours « Nombres premiers et petit théorème de Fermat » un exemple complet avec .
Nous allons ici illustrer le cas très simple par un petit tableau, afin de bien comprendre comment aborder l’algorithme Python.
Soit 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 à .
- .
Étape | Multiples de
( excepté) |
||
- L’ensemble des nombres premiers inférieurs ou égaux à est donc :
Algorithme Python
Algorithme Python
- Nous allons avoir besoin de la fontion , que nous importons du module :
- Nous définissons notre fonction , qui prendra donc en paramètre un entier supérieur ou égal à et qui affichera l’ensemble des nombres premiers inférieurs ou égaux à :
- Nous initialisons la liste avec l’ensemble des entiers compris entre et , par ordre croissant :
Ici, il faut faire attention.
En effet, nous allons parcourir la liste au moyen d’une boucle , 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 intermédiaire, et c’est dans cette liste que nous supprimerons les éléments. Puis, au moment adéquat, nous demanderons à ce que soit égale à .
- Pour l’instant, nous initialisons avec les mêmes valeurs que :
Il ne faut pas écrire : !
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 avec la valeur .
En effet, initialement, }}=\purple{\text{2}} , et nous commençons par chercher les multiples de .
- Tant que le nombre dont nous cherchons les multiples, soit , est inférieur ou égal à , nous continuons d’avancer dans la liste :
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 est inférieur ou égal à ».
Nous n’aurions alors pas eu besoin d’importer la fonction .
- Nous allons nous intéresser aux éléments de qui suivent , au moyen d’une boucle , sans considérer donc et les éléments qui le précèdent :
- Pour chacun de ces éléments, nous vérifions si c’est un multiple de , c’est-à-dire si le reste de la division euclidienne de par est égal à :
- Si c’est le cas, nous supprimons l’élément de la liste :
L’instruction supprime le premier élément de égal à .
- La liste 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 . Cette fonction nous convient donc très bien.
- Une fois la boucle sur terminée, nous pouvons cette fois y supprimer les multiples trouvés, en nous servant de :
- Nous allons à l’élément suivant de la liste :
Nous sortirons de la boucle dès que sera strictement supérieur à .
- contiendra alors uniquement l’ensemble des nombres premiers inférieurs ou égaux à .
- Nous indiquons d’abord combien il y en a.
- Puis nous affichons leur liste.
L’algorithme est terminé :
Vous pouvez chercher les nombres premiers inférieurs ou égaux à
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
, cela risque de prendre un peu de temps à l’algorithme pour renvoyer la liste des nombres premiers recherchés !n \purple{\text{n}}
Pour terminer, voici un petit exercice.
- Adapter d’abord le programme
pour que, au lieu d’afficher le nombre et la liste des nombres premiers inférieurs ou égaux àcrible \purple{\text{crible}} , il renvoie cette liste.n \purple{\text{n}} - Ensuite, s’en servir dans une fonction Python :
- qui prend en paramètres deux entiers naturels
etm \purple{\text{m}} tels quen \purple{\text{n}} etm ≤ n \purple{\text{m}} \leq \purple{\text{n}} ;n ≥ 2 \purple{\text{n}} \geq 2 - et qui affiche en retour la liste des nombres premiers compris entre
etm \purple{\text{m}} .n \purple{\text{n}}