Math
Le crible et la densité des nombres premiers
Faites le crible à la main sur des tuiles numérotées : prenez le diviseur suivant, prédisez où commence sa vague et regardez-la barrer ses multiples - ceux déjà barrés sont seulement touchés. À côté, pi(x) compté face aux approximations x/ln x et Li(x).
Ce qui se passe
Le crible d'Ératosthène sur un plateau de tuiles numérotées. Prenez le diviseur suivant - la plus petite tuile encore debout - et dites où sa vague commencera : le premier multiple encore debout est toujours p², car tout multiple plus petit k·p a le facteur plus petit k et est déjà barré. La vague passe ensuite sur p², p² + p, … : une tuile debout est barrée et prend la couleur de ce premier ; une tuile déjà barrée est seulement touchée et comptée, jamais barrée à nouveau. Les premiers trouvés se rangent sur une ligne sous le plateau. Le crible s'arrête quand le carré du diviseur suivant dépasse le plateau - tout composé jusqu'à N a un facteur au plus √N - et ce qui reste debout, ce sont les premiers. Sur un grand plateau les tuiles deviennent une carte dense ; une loupe sous le curseur lit les nombres. Le graphique à côté compte pi(x) jusqu'à sa propre limite face à deux approximations, x/ln x et Li(x) : la grossière sous-estime de quelques pour cent, Li est presque sur le compte, et 60180 est le dernier N sous deux millions où x/ln x se trompe de plus de dix pour cent.
Équations du module
Équations le crible compte pi(N) exactement - c'est la définition, non une estimation pi(10^3) = 168, pi(10^4) = 1229, pi(10^5) = 9592, pi(10^6) = 78498 N / ln N EST EN DESSOUS : à 10^3 de 13.83 %, à 10^4 de 11.66 %, à 10^5 de 9.45 %, à 10^6 de 7.79 % Li(N) = intégrale de 2 à N de dt/ln t se trompe d'une fraction de pour cent : 5.098 %, 1.309 %, 0.383 %, 0.164 % sur les mêmes décades Li(10^4) = 1245.092052, Li(10^6) = 78626.503996 la tâche : 60180 est le DERNIER N jusqu'à deux millions où N/ln N s'écarte de plus de dix pour cent (10.0004 %) ; à 60181 il est de 9.9990 % - trouvé en UN SEUL PASSAGE sur les comptages de préfixes, car l'erreur n'est PAS monotone : elle franchit la ligne des dix pour cent 159 fois, et la bissection qui se trouvait ici répondait 60180 coût du crible, deux quantités DIFFÉRENTES : premiers passages = N − pi(N) − 1 EXACTEMENT (8770 à 10^4, 921501 à 10^6) - chaque nombre composé est barré pour la première fois exactement une fois total des passages ~ somme de N/p pour p <= sqrt(N) (16981 contre 18028 à 10^4, rapport 0.9419; 0.9654 à 10^6) - le crible commence à p² et ne touche jamais les multiples plus petits plus grand écart entre nombres premiers : 8 après 89, 20 après 887, 36 après 9551, 72 après 31397 - tous encore inférieurs à ln²N
