ArithmétiqueNotion · Glossaire
crible d'Eratosthène
Le crible d'Ératosthène est un algorithme permettant de déterminer tous les nombres premiers inférieurs à un entier donné. Bien qu'il soit couramment attribué au mathématicien grec Ératosthène de Cyrène, ce procédé est également connu sous le nom d'algorithme de Nicomaque, du nom du mathématicien néo-pythagoricien Nicomaque de Gérase à qui certains historiens en attribuent la découverte. Le principe consiste à éliminer successivement, dans une liste d'entiers, tous les multiples de chaque nombre premier rencontré, les entiers non barrés étant les nombres premiers cherchés.
Sommaire
Ce que vous allez apprendre
- Identifier le geste d'élimination qui définit le crible.
- Reproduire le crible pour les entiers strictement inférieurs à 30.
- Savoir quand arrêter les éliminations et contrôler le résultat.
- Distinguer le crible d'un test de primalité et d'une factorisation.
En clair
Écrivez les entiers de 2 à 29. Gardez 2, puis rayez 4, 6, 8 et tous ses autres multiples. Le premier nombre encore visible est 3 : gardez-le et rayez ses multiples. Recommencez avec le prochain nombre non barré.
Peu à peu, seuls restent les nombres qui n'ont aucun diviseur autre que 1 et eux-mêmes. Ce geste de tri est le crible d'Ératosthène : les nombres premiers demeurent, tandis que les nombres composés disparaissent comme des grains trop gros dans un tamis.
Définition
Le crible d'Ératosthène est un algorithme qui fournit tous les nombres premiers strictement inférieurs à une borne entière donnée. Pour une borne appelée n, on dresse la liste des entiers de 2 à n − 1. On conserve 2, puis on barre ses multiples. On conserve ensuite le plus petit entier non barré et on élimine à son tour tous ses multiples. La même opération est répétée avec chaque nouveau nombre premier rencontré.
À la fin, les entiers non barrés sont exactement les nombres premiers inférieurs à n. Le procédé construit donc une liste complète jusqu'à une borne ; il ne se contente pas de décider si un seul entier est premier. Couramment attribué à Ératosthène de Cyrène, il est aussi appelé algorithme de Nicomaque. Certains historiens attribuent en effet sa découverte au mathématicien néo-pythagoricien Nicomaque de Gérase.
Un exemple, pas à pas
Cherchons les nombres premiers strictement inférieurs à 30. Les données sont la borne 30 et la liste des entiers de 2 à 29. Une grille permet de suivre le tri sans perdre les nombres déjà examinés.
1. Conservez 2. Barrez ses multiples : 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26 et 28.
2. Le premier entier non barré suivant est 3. Barrez ses multiples ; 9, 15, 21 et 27 sont les nouveaux nombres éliminés.
3. Le prochain entier non barré est 5. Parmi ses multiples, seul 25 n'était pas encore barré.
4. Le suivant est 7. Son carré vaut 49, au-delà de la borne 30 : tout nombre composé restant aurait déjà un facteur égal à 2, 3 ou 5. Le tri peut donc s'arrêter.
Le résultat est 2, 3, 5, 7, 11, 13, 17, 19, 23 et 29. Pour le contrôler, vérifiez que chacun des nombres supérieurs à 5 n'est divisible ni par 2, ni par 3, ni par 5.
En pratique
Sur papier, le crible convient lorsqu'on veut dresser une liste courte de nombres premiers. On écrit tous les entiers jusqu'à la borne, puis on barre les multiples par passages successifs. Pour vérifier un seul nombre, tester directement ses diviseurs demande moins de préparation.
Dans un programme, le crible est utile quand plusieurs calculs auront besoin de tous les nombres premiers inférieurs à la même borne. Si la question ne porte que sur un entier isolé, un test de primalité est plus adapté.
En classe ou dans un jeu de nombres, une grille colorée rend visibles les familles de multiples. Des critères de divisibilité peuvent accélérer le repérage de certains multiples, mais le crible reste le geste qui organise l'élimination complète.
À ne pas confondre
Un test de primalité. Le test répond pour un entier précis ; le crible produit tous les nombres premiers sous une borne. Pour 29, le test donne seulement « premier », tandis que le crible jusqu'à 30 fournit aussi 2, 3, 5, 7, 11, 13, 17, 19 et 23.
La décomposition en facteurs premiers. Une décomposition cherche les facteurs d'un nombre choisi ; le crible élimine les multiples dans une liste. Ainsi, le crible sous 30 repère 2, 3 et 5 comme premiers, mais il n'écrit pas la décomposition de 30.
Limites et pièges
Une borne inférieure ou égale à 2. La liste des entiers partant de 2 est vide, puisque seuls les nombres strictement inférieurs à la borne sont cherchés. Le résultat est donc une liste vide ; il ne faut pas y inclure 2.
Le nombre 1 placé dans la grille. Aucun passage ne le barrerait, mais cela ne le rend pas premier. La liste doit commencer à 2, car un nombre premier possède exactement deux diviseurs positifs distincts : 1 et lui-même.
Un arrêt trop précoce. Pour une borne appelée n et le prochain nombre premier non barré appelé p, les éliminations continuent tant que . Si ce critère est ignoré, un carré comme 25 peut rester visible. Il faut traiter 5 avant de conclure pour la borne 30.
Pour aller plus loin
nombre premier — Pour approfondir la propriété qui distingue les entiers conservés par le crible.
algorithme — Pour replacer cette suite d'éliminations dans la famille des procédures finies et ordonnées.
Critères de divisibilité — Pour reconnaître plus rapidement certains multiples à barrer.
L'inépuisable théorème des nombres premiers — Pour passer du calcul d'une liste finie à l'étude de la répartition des nombres premiers.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres