Sieb des Eratosthenes: Primzahlen finden

Eine Primzahl ist eine natürliche Zahl größer als 1 mit genau zwei verschiedenen Teilern: 1 und sich selbst. Zum Beispiel hat 7 nur die Teiler 1 und 7. Die Zahl 1 ist keine Primzahl, denn sie hat nur einen Teiler. Eine Zahl größer als 1, die keine Primzahl ist, heißt zusammengesetzt. So ist 12=3\cdot4 zusammengesetzt. Das Sieb streicht solche Zahlen als Vielfache kleinerer Primzahlen.

Schreibe die Zahlen von 2 bis 100 auf. Dann gehst du immer gleich vor: Die kleinste noch ungestrichene Zahl ist prim. Markiere sie und streiche ihre echten Vielfachen, also die größeren Vielfachen. Dann machst du mit der nächsten ungestrichenen Zahl weiter. Am Ende bleiben 25 Primzahlen stehen: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 und 97.

Bei einer Primzahl p musst du nicht alle Vielfachen von vorn prüfen. Jedes kleinere Vielfache hat die Form p \cdot k mit k < p und wurde schon in der Runde eines kleineren Faktors gestrichen. Deshalb beginnt die neue Streichrunde bei p^2. Auch das Ende ist klar: Für eine Grenze S brauchst du nur Primzahlen mit p^2 \le S. Jede zusammengesetzte Zahl bis S hat nämlich einen Primfaktor, der nicht größer als ihre Quadratwurzel ist. Hätte sie nur größere Faktoren, wäre schon das Produkt zweier solcher Faktoren größer als S.

Die jeweils kleinste ungestrichene Zahl kann kein Vielfaches einer kleineren Primzahl sein: Sonst wäre sie in einer früheren Runde gestrichen worden. Sie hat also keinen Teiler zwischen 1 und sich selbst und ist prim. Umgekehrt wird jede zusammengesetzte Zahl bis zur Grenze gestrichen. Sie besitzt einen Primfaktor, der höchstens so groß wie ihre Quadratwurzel ist. Spätestens in der Runde dieses Primfaktors wird sie erfasst. Das Sieb erzeugt eine vollständige Primzahlliste nur bis zur gewählten endlichen Grenze. Für sehr große Grenzen ist das einfache Verfahren aufwendig, auch wenn Quadratstart und Abbruchregel unnötige Schritte vermeiden.