Sieb des Eratosthenes
Sieb des Eratosthenes, ein auf Eratosthenes von Kyrene zurückgehender Algorithmus zur Ermittlung aller Primzahlen, die kleiner oder gleich einer vorgegebenen Grenze n sind.
Hierzu schreibt man die Zahlen 2 bis n auf und streicht nacheinander die Vielfachen von 2, 3, 5, 7 usw.; dabei braucht man nur bis zu den Vielfachen von √n zu gehen. Der für das Sieb des Eratosthenes erforderliche Rechenaufwand wächst mit n sehr stark an; deshalb ist die Methode
Quellenangabe