Générateur de liste de nombres premiers
Générez tous les nombres premiers dans l'intervalle de votre choix — de 2 à 10 000 000 — par crible d'Ératosthène segmenté. Statistiques, distribution, lacunes et jumeaux calculés instantanément. Calcul entièrement local, aucune donnée envoyée.
Paramètres du crible
Le crible d'Ératosthène : 2 200 ans d'algorithme, toujours optimal pour les petits n
Ératosthène de Cyrène (276–194 av. J.-C.) a décrit un procédé de sélection des nombres premiers qui reste, 22 siècles plus tard, l'algorithme le plus efficace pour lister tous les premiers jusqu'à n lorsque la mémoire disponible n'est pas un facteur limitant. Sa complexité O(n log log n) en temps et O(n) en mémoire n'a pas été améliorée de façon asymptotique pour ce problème spécifique — preuve que l'intuition géométrique grecque anticipait la théorie de la complexité moderne.
Distinction cruciale : tester si un nombre est premier (problème de primalité) et lister tous les premiers jusqu'à n (problème d'énumération) sont deux problèmes différents avec des solutions optimales différentes. Pour l'énumération, le crible d'Ératosthène bat systématiquement la division d'essai individuelle à partir de n ≈ 30, car chaque multiple n'est éliminé qu'une seule fois, sans division répétée.
Comment fonctionne le crible — et pourquoi la version segmentée change tout
Crible classique (simple)
- Créer un tableau booléen de taille n+1, tout initialisé à
vrai - Marquer 0 et 1 comme non-premiers
- Pour chaque p de 2 à √n : si p est encore
vrai, marquer tous les multiples de p (à partir de p²) commefaux - Collecter tous les indices restants à
vrai
Limite : pour n = 10⁷, le tableau booléen occupe ~10 Mo en RAM — acceptable. Pour n = 10⁹, il faudrait ~1 Go — problématique dans un navigateur.
Crible segmenté (cet outil)
- Calculer d'abord les premiers jusqu'à √n par crible classique
- Diviser [2, n] en segments de taille L (typiquement L = 32 768)
- Pour chaque segment, utiliser les premiers déjà trouvés pour barrer les multiples locaux
- La mémoire active est O(√n + L) — constante par rapport à n
Avantage : le segment tient dans le cache L1/L2 du processeur (32–256 Ko), ce qui accélère les accès mémoire d'un facteur 10 à 100 par rapport aux accès RAM.
| Limite n | Premiers trouvés π(n) | Mémoire (simple) | Temps (crible simple) | Temps (segmenté) |
|---|---|---|---|---|
| 1 000 | 168 | 1 Ko | < 0,1 ms | < 0,1 ms |
| 10 000 | 1 229 | 10 Ko | < 0,5 ms | < 0,5 ms |
| 100 000 | 9 592 | 100 Ko | ~2 ms | ~1 ms |
| 1 000 000 | 78 498 | 1 Mo | ~20 ms | ~8 ms |
| 10 000 000 | 664 579 | 10 Mo | ~250 ms | ~60 ms |
| 100 000 000 | 5 761 455 | 100 Mo | ~3 s | ~0,7 s |
3 utilisations concrètes d'une liste de premiers que les tutoriels n'expliquent pas
Usage 1 — Génération de clés RSA : constituer un « pool » de candidats premiers
Lors de la génération d'une clé RSA 2048 bits, la bibliothèque cryptographique ne tire pas un nombre au hasard et ne le teste pas. Elle constitue d'abord un crible des petits premiers (jusqu'à ~100 000) pour éliminer rapidement 80 % des candidats aléatoires avant d'appliquer un test de Miller-Rabin coûteux. Cette technique s'appelle le trial division sieving.
| Probabilité qu'un n aléatoire de 2048 bits soit premier | ≈ 1 / ln(2¹⁰²⁴) ≈ 1 / 710 |
| Avec crible des 1 229 premiers jusqu'à 10 000 | Élimine 80 % → teste seulement 1 candidat sur ~3,5 par Miller-Rabin |
| Gain de temps sur génération complète | Facteur ×4 à ×6 selon la plage |
| Nb. d'appels Miller-Rabin pour générer une clé RSA-2048 | ~100 à 200 tests en moyenne |
Notre liste de 9 592 premiers jusqu'à 100 000, générée en ~2 ms, suffit à implémenter un pre-sieve efficace pour des candidats de taille quelconque.
Usage 2 — Algorithmique compétitive : précalculer le crible une fois, l'utiliser des milliers de fois
Dans les compétitions de programmation (Codeforces, LeetCode, USACO), de nombreux problèmes demandent de tester la primalité de milliers de nombres dans un seul programme. La stratégie optimale est de pré-calculer le crible une seule fois en O(n log log n), puis de répondre à chaque requête en O(1) par simple accès au tableau.
| Méthode naïve : tester chaque n individuellement | O(√n) × k requêtes = O(k√n) |
| Crible précalculé une fois | O(n log log n) + O(k) = O(n log log n) |
| Pour k = 10 000 requêtes, n = 10⁶ | Naïf : 10⁷ ops — Crible : 5 × 10⁶ ops une seule fois |
| Pattern universel en compétition | « Sieve once, query forever » |
La liste générée ici peut être copiée en texte brut et collée directement dans un array JavaScript, Python ou C++ comme constante précalculée.
Usage 3 — Analyse musicale et composition : les tempéraments basés sur des rapports premiers
En acoustique musicale, les intervalles les plus consonants correspondent à des rapports de fréquences impliquant de petits nombres premiers. La limite première (prime limit) d'un système d'accordage détermine sa richesse harmonique : un système 5-limit (2, 3, 5) donne la gamme juste, un système 7-limit ajoute les septièmes naturelles, un 11-limit les quarts de ton, etc.
| Octave (2/1) | Rapport impliquant uniquement le premier 2 |
| Quinte juste (3/2) | Premiers 2 et 3 |
| Tierce majeure juste (5/4) | Premiers 2 et 5 — absente du tempérament pythagoricien (3-limit) |
| Septième harmonique (7/4) | Premier 7 — clairement audible dans le jazz et le blues |
| Fondement théorique | La liste des premiers détermine la hiérarchie des consonances naturelles |
Harry Partch (1901–1974) a construit des instruments microtonaux basés sur un système 11-limit, utilisant les 5 premiers {2, 3, 5, 7, 11}. La liste des premiers jusqu'à 100 suffit à explorer l'ensemble des rapports harmoniques pertinents pour la composition contemporaine.
Distribution des premiers : régularité globale, irrégularité locale
La distribution des nombres premiers est l'un des sujets les plus étudiés des mathématiques. Les résultats statistiques que cet outil calcule automatiquement s'inscrivent dans un contexte théorique riche :
Densité par décade
| Intervalle | π(n) | Densité | Moy. n/ln(n) |
|---|---|---|---|
| 1 → 10 | 4 | 40,0 % | — |
| 1 → 100 | 25 | 25,0 % | 21,7 (−13 %) |
| 1 → 1 000 | 168 | 16,8 % | 144,8 (−14 %) |
| 1 → 10 000 | 1 229 | 12,3 % | 1085 (−12 %) |
| 1 → 100 000 | 9 592 | 9,6 % | 8686 (−9 %) |
| 1 → 1 000 000 | 78 498 | 7,8 % | 72 382 (−8 %) |
| 1 → 10 000 000 | 664 579 | 6,6 % | 620 421 (−7 %) |
Lacunes remarquables dans [2, 10⁷]
Entre deux premiers consécutifs, les lacunes (gaps) sont distribuées de façon irrégulière. Les plus grandes lacunes dans notre plage :
| Après le premier | Lacune | Premier suivant |
|---|---|---|
| 7 | 4 | 11 |
| 23 | 6 | 29 |
| 89 | 8 | 97 |
| 113 | 14 | 127 |
| 9 551 | 36 | 9 587 |
| 31 397 | 72 | 31 469 |
| 155 921 | 86 | 156 007 |
| 360 653 | 96 | 360 749 |
| 2 010 733 | 148 | 2 010 881 |
| 4 652 353 | 154 | 4 652 507 |
La conjecture de Cramér (1936) : les lacunes entre premiers consécutifs autour de n sont au plus O(ln²n). En pratique, la plus grande lacune avant 10⁷ est 154 — contre ln²(4 652 353) ≈ 225. La conjecture semble confortable, mais n'est pas prouvée. Des variantes récentes (conjecture de Granville) suggèrent que la constante pourrait être supérieure à 1 dans ln²(n).
Premiers jumeaux : distribution et conjecture de Brun
Une paire de premiers jumeaux est une paire (p, p+2) où les deux sont premiers : (3,5), (5,7), (11,13), (17,19), (29,31)… Leur distribution se raréfie mais, contrairement aux intuitions, ne semble jamais s'arrêter complètement.
| Jusqu'à n | Paires jumelles | Densité relative |
|---|---|---|
| 100 | 8 | 32 % des premiers |
| 1 000 | 35 | 20,8 % |
| 10 000 | 205 | 16,7 % |
| 100 000 | 1 224 | 12,8 % |
| 1 000 000 | 8 169 | 10,4 % |
| 10 000 000 | 58 980 | 8,9 % |
Constante de Brun B₂
En 1919, Viggo Brun a prouvé que la somme des inverses des premiers jumeaux converge :
(1/3 + 1/5) + (1/5 + 1/7) + (1/11 + 1/13) + … = B₂ ≈ 1,902 160 583…
Cette convergence prouve que les jumeaux sont « rares » au sens analytique. En contraste, la somme des inverses de tous les premiers (série de Mertens) diverge logarithmiquement — les premiers sont donc plus « denses » que les jumeaux, dans un sens précis.
Optimisations du crible non documentées dans les tutoriels classiques
La plupart des implémentations en ligne du crible d'Ératosthène s'arrêtent à la version basique. Les optimisations suivantes réduisent le temps d'exécution d'un facteur 3 à 10 pour des intervalles larges :
| Optimisation | Principe | Gain typique | Implémentée ici |
|---|---|---|---|
| Exclure les pairs | Ne stocker que les impairs (2 traité séparément) — divise la mémoire par 2 | ×1,5 à ×2 | ✓ |
| Commencer à p² | Les multiples de p inférieurs à p² ont déjà été barrés par de plus petits premiers | ×1,2 | ✓ |
| Segmentation | Taille de segment = cache L1/L2 → accès mémoire ×10 plus rapides | ×3 à ×10 | ✓ (TypedArray Uint8) |
| Exclure multiples de 3 | Traiter 2 et 3 séparément, ne stocker que les ≡ 1,5 mod 6 | ×1,33 supplémentaire | Partiel |
| Roue mod 30 | Traiter 2,3,5 séparément, ne garder que 8 résidus sur 30 | ×1,875 supplémentaire | Pour grands n |
| Parallélisation | Web Workers pour traiter plusieurs segments simultanément | ×nb_cœurs | Non (simplicité) |
Le crible d'Ératosthène dans les langages modernes : pièges et bonnes pratiques 2026
Erreurs fréquentes d'implémentation
- Commencer les multiples à 2p au lieu de p² — coût inutile ×2
- Utiliser un tableau de booléens JavaScript ordinaires au lieu de
Uint8Array— mémoire ×8 - Oublier de traiter le cas p = 2 séparément dans les variantes impairs-seulement
- Tenter de générer jusqu'à 10⁹ en mémoire simple — crash navigateur (1 Go de RAM)
- Ne pas initialiser
sieve[0] = sieve[1] = falseavant de collecter les résultats - Confondre la limite du crible avec la limite de recherche d'un intervalle [a, b]
Bonnes pratiques 2026
- Utiliser
Uint8Array(JS) oubytearray(Python) — 8× moins de mémoire qu'un booléen - Pour un intervalle [a, b] avec a grand : crible segmenté depuis √b, pas depuis 2
- Toujours vérifier : le nombre de premiers jusqu'à n doit être ≈ n / ln(n) ± 15 %
- Pour n > 10⁷ dans un navigateur : utiliser un Web Worker pour ne pas bloquer l'UI
- Exporter en CSV compressé (gzip côté client via CompressionStream API) pour > 100 000 premiers
- Combiner avec le testeur de primalité individuel pour valider des cas limites
Decision guide — Quel outil choisir selon votre besoin ?
| Besoin | Outil recommandé | Pourquoi |
|---|---|---|
| Savoir si UN nombre est premier | Testeur de primalité | Plus rapide, avec décomposition et propriétés |
| Lister tous les premiers jusqu'à n ≤ 10⁷ | Cette page | Crible d'Ératosthène optimal, export intégré |
| Lister les premiers dans [a, b] avec a grand | Cette page (intervalle personnalisé) | Crible segmenté depuis √b, efficace même pour a = 9 900 000 |
| Calculer PGCD ou PPCM de deux nombres | Calculatrice PGCD | Algorithme d'Euclide, plus rapide que la factorisation |
| Simplifier une fraction | Simplificateur de fractions | Utilise le PGCD, pas la liste de premiers |
| Premiers > 10⁷ (cryptographie) | Bibliothèque dédiée (OpenSSL, libgmp) | Miller-Rabin déterministe, impossible à faire en navigateur |
Calculatrices complémentaires
Tester un nombre premier
Test individuel avec décomposition, τ(n), σ(n), voisins premiers
Plus grand facteur commun
PGCD par algorithme d'Euclide étendu
Plus petit multiple commun
PPCM = a × b / PGCD(a, b)
Simplifier une fraction
Réduction par PGCD — irréductible si PGCD = 1
Notation scientifique
Exprimer π(10⁷) = 664 579 en notation compacte
Logarithme
π(n) ≈ n / ln(n) — vérifier l'approximation du TNP