1. Das Sieb des Eratosthenes

Das Sieb des Eratosthenes erlaubt es, alle Primzahlen in einem Zahlenintervall 2, …, n bis zu einer beliebigen Grenze n zu gewinnen, indem zusammengesetzte Zahlen schrittweise gestrichen werden. Wir führen das Verfahren zunächst exemplarisch mit n = 100 als Grenze vor. Als Erstes schreiben wir alle Zahlen von 2 bis 100 auf:

Die quadratische Anordnung bietet sich für n = 100 an, ist aber nicht wesentlich. Wir könnten die Zahlen auch in einer Zeile oder kreisförmig anordnen.

 Wir markieren nun die Zahl 2 und streichen alle echten Vielfachen der 2:

Die erste nicht markierte und nicht gestrichene Zahl ist die 3. Wir markieren sie und streichen alle ihre echten Vielfachen:

Hier und im Folgenden zählen die Punkte, wie oft eine Zahl gestrichen wurde. Doppelpunkte ergeben sich genau bei den Vielfachen von 2 · 3, also von 6.

 Wir markieren nun die 5 und streichen wieder alle echten Vielfachen:

 Weiter geht es mit der 7:

 Anstelle nun mit der 11 fortzufahren, überlegen wir uns, dass eine zusammengesetzte Zahl k ≤ 100 einen Primteiler besitzt, der kleinergleich 10 ist. Denn andernfalls wäre die Zahl k, da sie keine Primzahl ist, größergleich 11² > 100. Diese Überlegung zeigt, dass wir das Sieben beenden können. Denn alle Zahlen zwischen 2 und 10 wurden bereits markiert oder gestrichen. Sie zeigt zudem, dass es genügt hätte, die Vielfachen p², p² + p, p² + 2p, … einer markierten Zahl p zu streichen. Denn die kleineren Vielfachen sind bereits gestrichen.

Unserer letzten Siebungstabelle können wir also entnehmen, dass es genau 25 Primzahlen im Intervall von 2 bis 100 gibt: 2, 3, 5, …, 83, 89, 97.

 Wir formulieren nun das Verfahren allgemein in algorithmischer Form.

 Ein Algorithmus beschreibt nur den Verlauf einer Berechnung und ist daher der Kategorie der Definitionen zuzuordnen. Was ein Algorithmus leistet wird in einem Satz formuliert und bewiesen (Korrektheit des Algorithmus). In unserem Fall lautet der Satz: Für alle n liefert der Algorithmus (in beiden Versionen) als Ergebnis genau die Primzahlen im Intervall von 2 bis n.

 Die Siebungstabellen enthalten weitere Informationen. Führen wir den Algorithmus in der Langform mit allen Primzahlen durch, so ist die Anzahl der Streichungen einer zusammengesetzten Zahl die Anzahl ihrer Primteiler. Die Vielfachheit eines Primteilers kann dagegen nicht abgelesen werden.

 Die folgende Tabelle zeigt, wieviele Zahlen im Intervall von 2, …, 100 in welchem Schritt die Siebung „überleben“:

Die rechte Spalte gibt an, wieviele Zahlen ausgesiebt werden. Am Ende bleiben genau 25 Primzahlen übrig.

 Für das Intervall von 2 bis 100² benötigen wir 25 Siebungen (mit den Primzahlen bis 100), um die 1229 Primzahlen dieses Intervalls zu erhalten:

 Das Sieb des Eratosthenes ist nicht nur ein effektives Verfahren zur Erzeugung von Primzahllisten, sondern es besitzt auch einen sehr hohen didaktischen, ästhetischen und weiter auch theoretischen Wert. Wir werden bei der Diskussion des Satzes von Mertens darauf zurückkommen. In den folgenden Essays betrachten wir zudem Varianten des Verfahrens.

Die Primzahlfakultät

 In unserer Darstellung des Siebverfahrens sind die Zahlen besonders ausgezeichnet, die von vielen Primzahlen geteilt werden. Die Diagramme weisen an den entsprechenden Stellen viele Punkte auf. Speziell gilt dies für die Produkte der ersten Primzahlen. Dies motiviert:

Die Definition ist analog zur Fakultät n! = 1 · 2 · … · n einer natürlichen Zahl. Im Gegensatz zur Fakultät werden nur die Primzahlen aufmultipliziert und zusammengesetzte Zahlen übersprungen. Damit gelten für alle n ≥ 1die Abschätzungen

n#  ≤  n!  und  p_n#  =  2 · 3 · 5 · 7 · 11 · … · p_n  ≤  p_nⁿ (mit der n-ten Primzahl p_n)

 Wir folgen der Konvention, das leere Produkt als 1 zu definieren (wie auch bei 0! = 1). Damit lauten die ersten Werte der Primzahlfakultät:

 Der Leser betrachte die Werte in den Diagrammen zum Siebverfahren. Der Eintrag bei 210 zeigt zum Beispiel vier Punkte, die den ersten vier Primzahlen entsprechen. Vier Punkte finden sich aber auch bei 2 · 5 · 7 · 11 = 770.

 Produkte von Primzahlen spielen im Beweis von Euklid eine Schlüsselrolle. Die Zahl n# + 1 ist durch keine Primzahl kleinergleich n teilbar. Folglich sind alle Primfaktoren dieser Zahl größer als n. Das Gleiche gilt auch für n! + 1 anstelle von n# + 1, aber die Primzahlfakultät ist im Allgemeinen wesentlich kleiner als die Fakultät von n. Unser Ergebnis über die Größenabschätzung der nächsten Primzahl können wir nun so angeben: