Crible des nombres premiers et spirale d'Ulam

Regardez le crible d'Ératosthène éliminer les nombres composés, ou observez les nombres premiers sur une spirale d'Ulam.

Exemple résolu — Crible des nombres premiers et spirale d'Ulam

π(100)	25 premiers
N / ln N	21.7(13.1% erreur)
Li(N)	29.1(16.3% erreur)
Paires jumelles	8 paires
Écart max	8

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Crible des nombres premiers et spirale d'Ulam

Le panneau affiche deux sortes de nombres bien distinctes, et il vaut la peine de les séparer avant de lire quoi que ce soit d’autre. π(N) est un décompte — combien de nombres premiers le crible a réellement laissés debout, 25 à N = 100 et 95 à N = 500, exact et non arrondi. Les deux lignes en dessous sont des estimations de ce même décompte. Le théorème des nombres premiers affirme que l’une d’elles obtient le bon rapport à la limite ; il n’affirme pas qu’elle obtient le bon nombre. Ce sont deux promesses très différentes, et c’est dans la colonne d’erreur que la différence se voit.

Ce que signifie chaque symbole

N: le plafond jusqu’auquel on crible, et la seule entrée. Le curseur va jusqu’à 10000.
π(N): le nombre de premiers n’excédant pas N. Compté, non estimé — c’est simplement le nombre de cases que le crible n’a pas rayées.
N / ln N: l’estimation la plus simple de ce décompte. Pour tout N que ce curseur atteint, elle est en dessous de la vérité.
Li(N): le logarithme intégral ∫₂ᴺ dt/ln t, une estimation plus fine. Pour tout N que ce curseur atteint, elle est au-dessus de la vérité.

D’où vient la formule

Le crible ne demande jamais si un nombre est premier. Il part de 2, raye tous les multiples de 2, passe au nombre suivant encore debout, raye tous ses multiples, et recommence. La primalité n’est pas testée ; elle est ce qui reste.
Il suffit de rayer les multiples des premiers jusqu’à √N. Si un nombre n ≤ N est composé, alors n = a·b avec a ≤ b, donc a ≤ √n ≤ √N — tout composé a un diviseur au plus égal à la racine, et a donc déjà été rayé au tour de ce diviseur. Cribler jusqu’à 100 ne demande que les passages de 2, 3, 5 et 7.
Comptez les survivants et vous obtenez π(N) exactement. Voilà pourquoi la ligne du haut est un fait et les deux d’en dessous des opinions : le crible produit le décompte comme sous-produit de son achèvement.
Comparez maintenant. Le théorème des nombres premiers dit que π(N) · ln N / N → 1 quand N grandit. Notez ce qu’il ne dit pas : un rapport tendant vers 1 autorise l’erreur relative à rester grande très longtemps — et la ligne suivante montre exactement cela.

Comment lire ce que vous voyez

Lisez les deux erreurs comme une course et faites varier N. À N = 100 l’estimation grossière mène : 13.1% contre 16.3% pour Li. Passez à N = 200 et cela s’inverse — 17.9% contre 6.9% — et cela ne s’inverse plus jamais. Mais le vrai point à observer, c’est ce que N/ln N ne fait pas. Sur deux ordres de grandeur son erreur donne 14.8%, 13.1%, 15.3%, 13.8%, 12.2% : elle fluctue et ne s’améliore quasiment pas. Li, sur le même intervalle, passe de 16.3% à 2.8%. Les deux estimations satisfont le théorème des nombres premiers ; une seule est utilisable aux tailles que vous pouvez voir. Les signes sont tout aussi constants — ici N/ln N reste sous le décompte à chaque N, Li reste au-dessus.

Suppose: Que N est assez petit pour être criblé intégralement : le décompte est exact parce que chaque nombre jusqu’à N est réellement stocké puis rayé, et c’est pourquoi le plafond est 10000 et non 10¹⁰. Les pourcentages d’erreur sont pris par rapport à π(N) : ils mesurent les estimations, jamais le décompte.
Ne tient plus quand: Li(N) > π(N) pour tout N que cette page peut atteindre, ce qui en fait ressembler une loi. Ce n’en est pas une. Littlewood a démontré en 1914 que la différence change de signe une infinité de fois, donc qu’il existe des N où Li sous-estime — et depuis un siècle personne n’en a exhibé un seul. Bays et Hudson ont ramené le premier changement sous environ 1.4×10³¹⁶ en 1999, et personne ne l’a resserré depuis. Cette page vous montre donc un motif dont on a prouvé qu’il n’est pas universel, et aucune position du curseur n’atteint le contre-exemple. Cet écart entre ce qui est visible et ce qui est vrai, c’est la forme honnête du sujet.

La raréfaction que vous voyez dans la grille est la partie que personne ne sait démontrer 🖖

La distribution précise des nombres premiers est régie par les zéros de la fonction zêta de Riemann ζ(s). Les 10¹³ zéros non triviaux connus se trouvent tous sur la droite critique Re(s) = 1/2. Démontrer cela pour tous les zéros donnerait les bornes les plus précises possibles pour le comptage des nombres premiers — et rapporterait le prix du millénaire d'un million de dollars. En 2025, cela reste non démontré.

Cribler plutôt que tester 🖖

Le crible d'Ératosthène trouve les nombres premiers par élimination, sans tester chaque nombre. Partez de 2, rayez tous ses multiples, sautez au nombre survivant suivant et recommencez ; ce qui n'est jamais rayé est premier. L'astuce astucieuse : pour cribler tous les nombres jusqu'à n, il suffit d'éliminer les multiples des nombres premiers jusqu'à √n. Ainsi, pour tout ce qui est inférieur à 100, rayer les multiples de 2, 3, 5 et 7 suffit.

Le gribouillage d'ennui d'Ulam 🖖

En 1963, le mathématicien Stanisław Ulam, s'ennuyant pendant un exposé, a griffonné les entiers en spirale carrée et colorié les nombres premiers — d'étonnantes stries diagonales sont apparues. Ces diagonales suivent des polynômes quadratiques riches en premiers, comme le n² + n + 41 d'Euler, qui donne un nombre premier pour chaque n de 0 à 39. Pourquoi certaines diagonales restent si denses demeure incompris à ce jour.

Problèmes entièrement résolus

Cribler à la main les 25 nombres premiers inférieurs à 100 5 étapes
Il y a 25 nombres premiers inférieurs à 100. Criblez-les à la main — cela demande moins de travail qu'on ne le penserait — puis testez le théorème des nombres premiers sur un échantillon bien trop petit pour lui.
1. L'économie réalisée par le crible est la raison pour laquelle il mérite son nom. Si n ≤ 100 est composé, il se décompose sous la forme ab, et le plus petit facteur ne peut pas dépasser √100 = 10. Ainsi, barrer les multiples de chaque nombre premier jusqu'à 10 élimine tous les nombres composés : quatre nombres premiers suffisent pour accomplir toute la tâche.
  
  $n \leq 100 composite ⟹ n = ab with min (a, b) \leq 100 = 10$
2. Rayez les multiples de 2, 3, 5 et 7, en commençant à chaque fois par son propre carré car tout ce qui précède a déjà été éliminé. Vingt-cinq nombres subsistent.
  
  $strike multiples of 2, 3, 5, 7 from 4 upward ⟹ π (100) = 25$
3. Le théorème des nombres premiers indique que le décompte est asymptotiquement N/ln N. Pour N = 100, cela donne 21,7.
  
  $π (N) \sim \frac{N}{ln N} : \frac{100}{ln 100} = \frac{100}{4.6052} = 21.7$
4. Il est trop faible de 13 %, ce qui est tout à fait acceptable pour un résultat asymptotique à 100. Pris dans l'autre sens, il reste utile ici : la densité des nombres premiers au voisinage de N est 1/ln N, de sorte qu'environ 22 % des nombres proches de 100 sont premiers, contre 7,2 % près d'un million. Les nombres premiers se raréfient de façon logarithmique, c'est-à-dire très lentement.
  
  $\frac{25 - 21.7}{25} = 13.1%, \frac{1}{ln 100} = 21.7% vs \frac{1}{ln 1 0 ^{6}} = 7.2%$
5. Les écarts concordent. L'écart moyen en dessous de 100 est 100/25 = 4, et le plus grand est 8 — la suite allant de 89 à 97. Deux fois la moyenne, et rien de pire.
  
  $mean gap = \frac{100}{25} = 4, largest = 97 - 89 = 8$
Réponse

Le crible donne π(100) = 25 et l'outil affiche l'estimation à 21,7, trop faible de 13,1 %. Cette erreur ne signifie pas que le théorème échoue ; elle rend visible sa vitesse de convergence, et cette convergence est réputée lente — poussez N jusqu'à 10 000, soit quatre ordres de grandeur plus haut, et l'estimation reste inférieure à deux chiffres. Ce qui est valable à toutes les échelles, c'est la mesure de densité. Un nombre sur 4,6 près de 100 est premier, un sur 13,8 près d'un million, et comme le logarithme croît si lentement, les nombres premiers ne s'épuisent jamais et ne deviennent même jamais véritablement rares.

$π (100) = 25 from four primes; \frac{N}{ln N} = 21.7 (13.1% low)$
L'estimation évidente pour 8 paires de jumeaux sous 100 6 étapes
Le panneau compte 25 nombres premiers sous 100 et 8 paires de jumeaux. Le premier nombre a une estimation célèbre qui tombe à 13 % près. Essayez l'estimation évidente pour le second — et regardez-la manquer d'un facteur qui porte un nom.
1. Prenez le décompte et l'estimation affichés comme point de départ : près de N, un nombre est premier avec une probabilité d'environ 1/ln N, soit à N = 100 quelque 0,2171.
  
  $π (100) = 25, \frac{N}{ln N} = \frac{100}{4.6052} = 21.7$
2. Supposez maintenant n et n+2 indépendants. Si chacun est premier avec la probabilité 1/ln N, les deux le sont avec le carré de celle-ci.
  
  $P_{1} \approx \frac{1}{ln N} = 0.2171 ⟹ P_{2} \approx P_{1}^{2} = \frac{1}{( ln N ) ^{2}}$
3. Multipliez par N et comparez à l'outil. L'estimation annonce 4,72 paires jumelles sous 100 ; le crible en a trouvé 8. Ce n'est pas un léger écart : il manque 40 %.
  
  $N P_{2} = \frac{100}{21.208} = 4.72 ⟷ π_{2} (100) = 8$
4. L'indépendance est le faux pas, et un seul nombre premier le montre. Prenez un premier impair p : un n au hasard est éliminé par p une fois sur p, mais la paire l'est dès que n ou n+2 est divisible par p, soit deux résidus sur p. Le taux de survie vaut donc (p−2)/p, et non le carré de (p−1)/p que l'indépendance supposait.
  
  $p > 2 : n \equiv 0 \lor n + 2 \equiv 0 (mod p) ⟹ \frac{p - 2}{p} \neq = (\frac{p - 1}{p})^{2}$
5. Multipliez cette correction sur tous les premiers impairs et elle converge vers une constante. Son double vaut 1,3203, et l'appliquer porte l'estimation à 6,23.
  
  $2 C_{2} = 2 p > 2 \prod \frac{p ( p - 2 )}{( p - 1 ) ^{2}} = 1.3203 ⟹ 1.3203 \times 4.72 = 6.23$
6. Toujours en dessous de 8 à N = 100 — l'estimation est asymptotique et 100 est un petit nombre. Elle converge : 156 paires prévues sous 10⁴, 6917 sous 10⁶.
  
  $N = 1 0^{4} : 156 N = 1 0^{6} : 6917$
Réponse

Le décompte naïf donne 4,72, le corrigé 6,23, et la vérité est 8 — et le facteur correctif 1,3203 est un produit infini sur les nombres premiers. Cette constante est le prix de l'hypothèse d'indépendance là où il n'y en a pas, et elle a la forme de presque toute question difficile du domaine : les premiers sont assez aléatoires pour qu'une heuristique marche, et assez structurés pour qu'elle réclame une correction que personne ne sait déduire de rien. La conjecture des nombres premiers jumeaux affirme que cette estimation ne manque jamais de paires, et elle reste ouverte.

$π_{2} (N) \sim 2 C_{2} \frac{N}{( ln N ) ^{2}}, 2 C_{2} = 1.3203 : 4.72 \to 6.23 ⟷ 8$

Références (4)

Why the page’s most convincing pattern is not a law — the difference changes sign infinitely often: J. E. Littlewood, "Sur la distribution des nombres premiers." Comptes Rendus de l’Académie des Sciences, Paris 158, 1869–1872, 1914. No DOI: the volume predates them.
How far the first sign change has been pinned down, and where the 1.4×10³¹⁶ comes from: C. Bays & R. H. Hudson, "A new bound for the smallest x with π(x) > li(x)." Mathematics of Computation 69, 1285–1296, 1999.
How far the Riemann hypothesis has actually been verified — note this is a bound on height, a different measure from a count of zeros: D. J. Platt & T. S. Trudgian, "The Riemann hypothesis is true up to 3·10^12." Bulletin of the London Mathematical Society 53, 792–797, 2021.
The prize, and its official problem statement: Clay Mathematics Institute, Millennium Prize Problems — the Riemann Hypothesis.

Par l’équipe 42Math · Mis à jour 2026-06-20

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Mathématiques →

Exemples de problèmes

Petit (100) - Criblez jusqu'à 100 et l'estimation rudimentaire l'emporte. L'expression N/ln N donne 21,7, soit une erreur de 13,1 %, alors que Li(100) = 29,1 s'écarte du total de 16,3 %. C'est la seule configuration où cela se produit. Passez à 500 pour voir l'erreur de Li chuter à 6,2 %, tandis que celle de N/ln N plafonne à 15,3 % pour s'y maintenir.
Moyen (500) - Vous trouverez 95 nombres premiers avant 500, répartis en 24 paires de jumeaux. Le plus grand écart atteint 14 lors du saut de 113 à 127, une plage vierge de tout nombre premier. Ce record tient ensuite jusqu'à 523, seuil auquel s'ouvre un écart de 18. Un écart record ne s'élargit pas de façon continue avec N. Il patiente.
Colonnes froides - On dénombre 154 nombres premiers en deçà de 900, formant 35 paires de jumeaux. Poursuivez jusqu'à 1000 pour en trouver 14 de plus, sans découvrir la moindre paire supplémentaire : la dernière réunit 881 et 883. Les jumeaux se raréfient plus vite que les nombres premiers eux-mêmes. Savoir s'ils finissent par disparaître totalement reste une question ouverte.
Ulam 400 - Vous retrouvez les mêmes 78 nombres premiers que dans le mode grille, replacés sur une spirale carrée. La nature des nombres n'a pas changé. Les bandes diagonales émergent uniquement de la position que la spirale attribue à chaque entier. Voilà pourquoi une image peut suggérer un motif que l'arithmétique n'a pas confirmé.
TNP (1000) - π(1000) = 168. La formule N/ln N donne 144,8, affichant une erreur de 13,8 % ; Li(1000) donne 177,0, avec une erreur de 5,3 %. Toutes deux respectent le théorème des nombres premiers. Pour chaque valeur de N permise par cet outil, seule l'une de ces estimations s'avère vraiment utile. Notez que Li se place systématiquement au-dessus du compte réel.