Sieb des Eratosthenes

Das Sieb des Eratosthenes ist ein Algorithmus zur Bestimmung einer Liste oder Tabelle aller Primzahlen kleiner oder gleich einer vorgegebenen Zahl. Es ist nach dem griechischen Mathematiker Eratosthenes benannt. Allerdings hat Eratosthenes, der im 3. Jahrhundert v. Chr. lebte, das Verfahren nicht entdeckt, sondern nur die Bezeichnung „Sieb“ für das schon lange vor seiner Zeit bekannte Verfahren eingeführt.

Es ist das einfachste Beispiel von in der analytischen Zahlentheorie verwendeten ausgefeilten Methoden der Siebtheorie (zum Beispiel von Adrien-Marie Legendre, Viggo Brun, Atle Selberg, Alfred Renyi, Pál Turán, Juri Linnik, Klaus Friedrich Roth, Enrico Bombieri, Askold Winogradow, John Barkley Rosser, Hugh Montgomery, John Friedlander, Henryk Iwaniec, Roger Heath-Brown). Der erste Schritt war die Verbesserung bzw. Umformulierung von Eratosthenes’ Sieb durch Legendre mit Hilfe der Möbiusfunktion mit zugehöriger Legendre-Identität und der Anfang moderner Siebmethoden war dessen Verbesserung durch Brun 1915.