Math
Das Sieb und die Dichte der Primzahlen
Arbeiten Sie das Sieb von Hand auf nummerierten Kacheln ab: Nehmen Sie den nächsten Teiler, sagen Sie voraus, wo seine Welle beginnt, und sehen Sie zu, wie sie seine Vielfachen streicht - bereits gestrichene werden nur berührt. Daneben pi(x) gezählt gegen die Näherungen x/ln x und Li(x).
Was passiert
Das Sieb des Eratosthenes auf einem Brett nummerierter Kacheln. Nehmen Sie den nächsten Teiler - die kleinste noch stehende Kachel - und sagen Sie, wo seine Welle beginnt: Das erste noch stehende Vielfache ist immer p², denn jedes kleinere Vielfache k·p hat den kleineren Faktor k und ist schon draußen. Dann läuft die Welle über p², p² + p, …: Eine stehende Kachel wird gestrichen und nimmt die Farbe dieser Primzahl an; eine bereits gestrichene wird nur berührt und gezählt, nie erneut gestrichen. Gefundene Primzahlen sammeln sich in einer Reihe unter dem Brett. Das Sieb hält, wenn das Quadrat des nächsten Teilers über das Brett hinausgeht - jede zusammengesetzte Zahl bis N hat einen Faktor höchstens √N -, und was noch steht, sind die Primzahlen. Auf einem großen Brett werden die Kacheln zur dichten Karte; eine Lupe unter dem Cursor liest die Zahlen. Das Diagramm daneben zählt pi(x) bis zu seiner eigenen Grenze gegen zwei Näherungen, x/ln x und Li(x): Die grobe unterschätzt um Prozente, Li liegt fast auf der Zählung, und 60180 ist das letzte N unter zwei Millionen, bei dem x/ln x um mehr als zehn Prozent danebenliegt.
Gleichungen des Moduls
Gleichungen das Sieb zählt pi(N) exakt - das ist die Definition, keine Schätzung pi(10^3) = 168, pi(10^4) = 1229, pi(10^5) = 9592, pi(10^6) = 78498 N / ln N UNTERSCHÄTZT: bei 10^3 um 13.83 %, bei 10^4 um 11.66 %, bei 10^5 um 9.45 %, bei 10^6 um 7.79 % Li(N) = Integral von 2 bis N über dt/ln t verfehlt um einen Bruchteil eines Prozents: 5.098 %, 1.309 %, 0.383 %, 0.164 % auf denselben Dekaden Li(10^4) = 1245.092052, Li(10^6) = 78626.503996 die Aufgabe: 60180 ist das LETZTE N bis zwei Millionen, bei dem N/ln N um mehr als zehn Prozent abweicht (10.0004 %); bei 60181 sind es 9.9990 % - gefunden in EINEM DURCHLAUF über die Präfixzählungen, weil der Fehler NICHT monoton ist: er überquert die Zehn-Prozent-Linie 159 Mal, und die Bisektion, die hier früher stand, antwortete 60180 Kosten des Siebs, zwei VERSCHIEDENE Größen: erste Streichungen = N − pi(N) − 1 EXAKT (8770 bei 10^4, 921501 bei 10^6) - jede zusammengesetzte Zahl wird genau einmal zum ersten Mal gestrichen Berührungen insgesamt ~ Summe von N/p über p <= sqrt(N) (16981 gegenüber 18028 bei 10^4, Verhältnis 0.9419; 0.9654 bei 10^6) - das Sieb beginnt bei p² und berührt die kleineren Vielfachen nie größte Primzahllücke: 8 nach 89, 20 nach 887, 36 nach 9551, 72 nach 31397 - alle noch unterhalb von ln²N
