Passer au contenu principal
Tangente
Abonnez-Vous
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.
Crible des entiers de 2 à 29 Les nombres premiers sont conservés dans des cases jaunes et les nombres composés sont barrés en rouge. Entiers de 2 à 29 2345678 9101112131415 16171819202122 23242526272829 Premier conservé Multiple éliminé
Sous la borne 30, dix nombres premiers restent en jaune après l'élimination des multiples barrés en rouge.
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 p2<n. 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.
Continuez avec Tangente

Explorez les mathématiques autrement

Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.

Découvrir les offres

Articles qui en parlent

La factorisation des grands entiers :
Histoire et Culture

La factorisation des grands entiers :

Le système de cryptographie le plus répandu repose sur l’utilisation de très grands entiers, dont la factorisation reste hors de portée de nos ordinateurs. Dès le XVIIe siècle, Mersenne et Fermat se sont penchés sur la décomposition en facteurs premiers de très grands nombres ; leurs travaux ont inspiré les algorithmes modernes de factorisation.

Karine Brodsky24 oct. 2022
Ce nombre est-il premier ?
Maths pour tous

Ce nombre est-il premier ?

Les nombres premiers constituent l’ossature de l’arithmétique. Si la recherche de leur répartition fait l’objet des recherches les plus modernes, savoir déterminer de tête la primalité d’un nombre est un excellent exercice, à la fois ludique et créatif.

FRANCOIS LAVALLOU20 août 2025
L'inépuisable théorème des nombres premiers
Maths pour tous

L'inépuisable théorème des nombres premiers

Les nombres premiers sont une source intarissable de surprises mathématiques : ils sont infinis mais rares et, quand on veut les dénombrer, on voit apparaître des fonctions transcendantes, comme la fonction zêta de Riemann, a priori très éloignées de l'arithmétique.

Hervé Lehning7 juil. 2016
Bienvenue dans les maths de l'Antiquité !
Histoire et Culture

Bienvenue dans les maths de l'Antiquité !

BERTRAND HAUCHECORNE30 juin 2019
De la suite dans les idées
Maths pour tous

De la suite dans les idées

Les algorithmes qui permettent de construire des suites d'entiers à partir d'un nombre donné sont variés. Nombre d'entre eux ont été imaginés au XXème siècle par des mathématiciens connus (Ulam, Kaprekar, Sloane...) et débouchent sur des résultats parfois surprenants, dont certains restent encore à l'état de conjectures.

Fabien AOUSTIN4 nov. 2020