Sciences · Mathématiques
Le crible d’Ératosthène
Le crible d’Ératosthène donne tous les nombres premiers jusqu’à un entier n : on écrit les nombres de 2 à n, puis on barre les multiples de 2, de 3, de 5… Les nombres jamais barrés sont premiers.
Mis à jour le 4 min de lecture
Plutôt que de tester chaque nombre un par un, le crible procède à l’envers : il élimine tous les nombres qui ne peuvent pas être premiers. La méthode est attribuée à Ératosthène de Cyrène (IIIe siècle av. J.-C.), savant grec qui dirigea la bibliothèque d’Alexandrie et estima aussi la circonférence de la Terre. Plus de deux mille ans après, c’est encore l’un des moyens les plus efficaces de lister les petits nombres premiers.
La méthode pas à pas
- Écrire tous les entiers de 2 à n (1 n’est pas premier).
- Le premier nombre non barré, 2, est premier. Barrer tous ses multiples à partir de 2² = 4 : 4, 6, 8, 10…
- Le nombre suivant non barré, 3, est premier. Barrer ses multiples à partir de 3² = 9 : 9, 12, 15…
- Recommencer avec 5 (à partir de 25), puis 7 (à partir de 49), et ainsi de suite.
- S’arrêter dès que le carré du nombre suivant dépasse n. Tous les nombres restants non barrés sont premiers.
Exemple : les nombres premiers jusqu’à 100
Comme √100 = 10, il suffit de barrer les multiples de 2, 3, 5 et 7.
| Étape | On barre les multiples de | À partir de | Exemples barrés |
|---|---|---|---|
| 1 | 2 | 4 | 4, 6, 8, …, 100 (49 nombres) |
| 2 | 3 | 9 | 9, 15, 21, 27, 33… (impairs restants) |
| 3 | 5 | 25 | 25, 35, 55, 65, 85, 95 |
| 4 | 7 | 49 | 49, 77, 91 |
Le prochain candidat est 11, et 11² = 121 > 100 : on s’arrête. Il reste 25 nombres premiers :
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
Pourquoi commencer à p² et s’arrêter à √n ?
- Quand on traite le nombre premier p, ses multiples plus petits que p² (2p, 3p…) ont un facteur plus petit que p et ont déjà été barrés. Pour 7 : 14, 21, 28, 35, 42 sont déjà barrés comme multiples de 2, 3 ou 5.
- Un nombre composé n s’écrit
a × bavec a ≤ b, donca² ≤ n, soita ≤ √n. Tout nombre composé jusqu’à n a donc un facteur premier au plus égal à √n, et sera barré avant cette limite.
Le crible comme algorithme
Le crible est un exemple classique d'algorithme. En pseudo-code :
- créer un tableau
estPremier[2..n]rempli de « vrai » ; - pour p de 2 tant que
p × p ≤ n: siestPremier[p], mettre à « faux »estPremier[p²],estPremier[p² + p], … ; - les indices restés « vrai » sont les nombres premiers.
Sa complexité est d’environ n × log(log n) opérations : quasiment linéaire. Il reste très rapide jusqu’à plusieurs milliards, sa limite étant surtout la mémoire nécessaire au tableau. Des variantes (crible segmenté, crible d’Atkin, crible de Sundaram) améliorent ces performances.
Ce que le crible fait voir
- Les nombres premiers se raréfient : 25 jusqu’à 100, 168 jusqu’à 1 000, 1 229 jusqu’à 10 000. Leur densité autour de n est d’environ
1 / ln n(théorème des nombres premiers ; voir le logarithme). - Des paires comme (11, 13), (17, 19) ou (41, 43) apparaissent : ce sont les nombres premiers jumeaux.
- Le crible ne fournit pas de formule : il ne permet pas de savoir directement si un nombre isolé très grand est premier.
Erreurs fréquentes
- Garder 1 : 1 n’est pas premier, on commence à 2.
- Barrer le nombre premier lui-même : on barre ses multiples, pas lui.
- Continuer inutilement : au-delà de √n, plus rien n’est barré.
Questions fréquentes
Combien y a-t-il de nombres premiers inférieurs à 100 ?
Il y en a 25, de 2 à 97.
Pourquoi le crible s’arrête-t-il à la racine carrée de n ?
Parce que tout nombre composé inférieur ou égal à n a au moins un facteur premier inférieur ou égal à √n. Il a donc déjà été barré.
Qui était Ératosthène ?
Un savant grec de Cyrène (vers 276-194 av. J.-C.), mathématicien, géographe et astronome, directeur de la bibliothèque d’Alexandrie. Il est connu pour sa mesure de la circonférence terrestre.
Le crible permet-il de trouver de très grands nombres premiers ?
Non : il exige de traiter tous les nombres jusqu’à n. Les records (nombres de Mersenne de plusieurs millions de chiffres) sont obtenus avec des tests spécialisés.