Das Sieb des Eratosthenes ist ein Algorithmus zum Finden aller Primzahlen bis zu einer gegebenen Grenze. Der Algorithmus ist nach dem antiken griechischen Mathematiker Eratosthenes benannt, der im 3. Jahrhundert v. Chr. lebte und einer der ersten war, der eine Methode zum Auffinden von Primzahlen entwickelte.
Der Algorithmus funktioniert wie folgt: Man erstellt eine Liste aller Zahlen von 2 bis zu einer gegebenen Grenze, die man prüfen möchte. Dann beginnt man mit der kleinsten Primzahl, die 2 ist, und streicht alle Vielfachen von 2 aus der Liste (mit Ausnahme von 2 selbst). Als nächstes geht man zur nächsten ungestrichenen Zahl und streicht alle Vielfachen dieser Zahl aus der Liste. Man fährt auf diese Weise fort, bis man alle Zahlen bis zur Grenze überprüft hat. Die übrig gebliebenen Zahlen in der Liste sind dann alle Primzahlen.
Ein Beispiel soll das Vorgehen verdeutlichen: Wenn man alle Primzahlen bis 30 finden möchte, beginnt man mit der Zahl 2 und streicht alle Vielfachen von 2 aus der Liste (also 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28 und 30). Als nächstes geht man zur nächsten ungestrichenen Zahl, die 3 ist, und streicht alle Vielfachen von 3 aus der Liste (also 9, 15, 21 und 27). Man fährt fort mit der nächsten ungestrichenen Zahl, die 5 ist, und streicht alle Vielfachen von 5 aus der Liste (also 25). Da es keine ungestrichenen Zahlen mehr gibt, sind alle übrigen Zahlen in der Liste Primzahlen (2, 3, 5, 7, 11, 13, 17, 19, 23 und 29).
Dieser Algorithmus ist effizient, weil man nur jede Zahl einmal überprüfen muss und alle Vielfachen gestrichen werden können, ohne sie tatsächlich zu berechnen. Die Laufzeit des Algorithmus beträgt O(n log log n), wobei n die Grenze ist, bis zu der Primzahlen gefunden werden sollen.
In der Praxis wird der Algorithmus oft verwendet, um Primzahlen für kryptographische Anwendungen zu generieren, da Primzahlen in der Kryptographie eine wichtige Rolle spielen.