Générateur du Crible d'Ératosthène (Gratuit) – Liste de nombres premiers et N-ième premier
Indiquez une limite supérieure N pour générer une liste de nombres premiers avec le Crible d'Ératosthène, visualisée étape par étape. Recherchez aussi le N-ième nombre premier (jusqu'au 1 000 000e) — gratuit, dans le navigateur, sans inscription.
Crible d'Ératosthène de 1 à 100 (tableau de référence)
Les cellules vertes sont des nombres premiers ; les autres ont été éliminées par le crible.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
| 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |
| 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |
| 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 |
| 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |
| 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 |
| 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |
1 n'est ni premier ni composé, il n'est donc pas coloré.
Ce que fait le crible d'Ératosthène
Le crible d'Ératosthène est l'algorithme classique de recherche des nombres premiers, du nom du savant grec du IIIe siècle avant notre ère. L'idée est d'une simplicité saisissante : prenez chaque nombre dans l'ordre à partir de deux, déclarez-le premier s'il n'a pas encore été rayé, puis rayez tous ses multiples. Rayez les multiples de deux, puis ceux du trois qui a survécu, ensuite ceux du cinq ; répétez jusqu'à la racine carrée de votre limite et tout nombre encore debout est premier.
Donnez une limite supérieure à cet outil et il produit la liste des nombres premiers jusqu'à un million. Il affiche le processus de rayage étape par étape, de sorte que vous pouvez suivre de vos propres yeux quel nombre premier a éliminé quels nombres. Il fonctionne aussi à l'envers et répond à la question « quel est le N-ième nombre premier ? » pour des rangs allant jusqu'au millionième. Tout est calculé dans votre navigateur : rien de ce que vous saisissez n'en sort.
Comment produire une liste de nombres premiers
- Saisissez la limite supérieure N Indiquez un entier compris entre 2 et 1 000 000. Commencer par une petite valeur comme 100 rend le mécanisme du crible bien plus lisible.
- Vérifiez le décompte et le plus grand nombre premier Vous obtenez combien de nombres premiers se trouvent jusqu'à N — noté π(N) — ainsi que le plus grand d'entre eux.
- Suivez les étapes de rayage Pour les petites limites, chaque étape indique quel nombre premier a été employé et quels nombres il a éliminés.
- Recherchez le N-ième nombre premier Saisissez un rang et l'outil renvoie le nombre premier qui l'occupe.
Astuces pour en tirer le meilleur parti
- Le Crible d'Ératosthène liste efficacement tous les nombres premiers jusqu'à N en barrant les multiples de chaque premier trouvé, à partir de 2.
- Réglez la limite supérieure N à 400 ou moins pour voir exactement quel premier a éliminé quel nombre, étape par étape.
- La recherche du N-ième premier prend en charge des requêtes comme « quel est le 1 000 000e nombre premier », utile pour confirmer l'existence de très grands nombres premiers.
- Tout s'exécute localement dans votre navigateur — la liste de premiers générée n'est jamais envoyée à un serveur.
Dans quels cas cela sert
Étudier les algorithmes
Le crible est l'exemple canonique de la complexité O(n log log n), et le voir tourner ancre l'idée.
Vérifier votre propre implémentation
Comparez la sortie d'un crible que vous avez écrit avec celle-ci pour confirmer qu'il produit la bonne suite.
Observer la répartition des nombres premiers
Faire varier la limite et regarder croître π(N) donne une intuition du théorème des nombres premiers et de son comportement en N / log N.
Se documenter sur la cryptographie
Les schémas à clé publique comme RSA reposent sur de grands nombres premiers ; voilà une porte d'entrée pour saisir leur densité.
Les termes des nombres premiers et du crible
- Nombre premier
- Un entier naturel supérieur ou égal à deux dont les seuls diviseurs positifs sont un et lui-même. Un n'est pas compté comme premier.
- Nombre composé
- Un entier naturel supérieur ou égal à deux qui n'est pas premier. Ce sont ces nombres que le crible raye.
- π(N)
- La fonction donnant le nombre de nombres premiers jusqu'à N, dite fonction de compte des nombres premiers.
- Rayage
- Le fait de marquer les multiples d'un nombre premier pour les exclure des candidats. C'est cette opération qui donne son nom à l'algorithme.
- Pourquoi la racine carrée suffit
- Tout multiple d'un nombre premier supérieur à la racine carrée de N a déjà été rayé comme multiple d'un nombre premier plus petit.
- Théorème des nombres premiers
- Le résultat selon lequel π(N) est asymptotique à N / log N, décrivant la vitesse à laquelle les nombres premiers se raréfient.
Questions fréquentes
Anecdote — Pourquoi un algorithme vieux de 2 000 ans est encore utilisé
Le Crible d'Ératosthène est l'un des plus anciens algorithmes de génération de nombres premiers encore connus, attribué au savant grec Ératosthène, qui fut bibliothécaire en chef de la Bibliothèque d'Alexandrie au IIIe siècle av. J.-C. Le fait qu'une méthode conçue il y a plus de deux mille ans soit encore enseignée aujourd'hui dans les cours d'informatique témoigne de son élégante simplicité.
Le mécanisme est étonnamment simple : on liste les entiers à partir de 2, on considère le plus petit nombre non encore marqué comme premier, et on barre tous ses multiples. En répétant cette opération jusqu'à √N, tous les nombres premiers jusqu'à N sont révélés. Pour générer une liste complète de premiers, c'est bien plus efficace que de tester chaque nombre individuellement par division d'essai.
La recherche de nombres premiers gigantesques se poursuit aujourd'hui — des projets de calcul distribué comme GIMPS (Great Internet Mersenne Prime Search) continuent de découvrir des nombres premiers de Mersenne comptant des dizaines de millions de chiffres. Le crible lui-même n'est pas utilisé pour trouver des premiers aussi grands, mais son idée centrale — éliminer mécaniquement les multiples — sous-tend des algorithmes de test de primalité plus avancés.