4. Das Sieb von Euler

Wir haben gesehen, dass beim Sieb des Eratosthenes viele Zahlen mehrfach gestrichen werden. Die folgende Variante des Verfahrens vermeidet mehrfache Streichungen und ist aus algorithmischer Sicht damit noch effektiver, wenn es uns nur darauf ankommt, alle Primzahlen eines Intervalls zu finden:

Das Sieb von Euler

Sei n eine beliebige natürliche Zahl. Wir erstellen eine Liste aller Zahlen von 2 bis n. Nun verfahren wir wie beim Sieb des Eratosthenes in der schnellen Version, wobei wir für eine neu markierte Primzahl p nicht mehr alle Vielfachen p², p² + p, p² + 2p, … von p ab p² streichen, sondern nur noch alle Produkte von p mit den bislang weder markierten noch gestrichenen Zahlen (beginnend mit p²).

(Das Verfahren ist durch die Eulersche Produktformel für die Zeta-Funktion motiviert, explizit scheint es Euler nicht betrachtet zu haben.)

Für n = 100 werden im ersten Durchgang wieder alle echten Vielfachen der 2 gestrichen. Die überlebenden nicht markierten Zahlen sind 3, 5, 7, 9, … Wir markieren die 3 und streichen alle Produkte

3 · 3, 3 · 5, 3 · 7, 3 · 9, …

Die überlebenden und nicht markierten Zahlen sind nun 5, 7, 11, 13, … Wir markieren die 5 und streichen alle Produkte

5 · 5, 5 · 7, 5 · 11, 5 · 13, …

Wie früher genügt es, das Verfahren solange durchzuführen, bis alle Zahlen kleinergleich 10 markiert oder gestrichen sind. Die folgenden Diagramme zeigen den Verlauf für n = 100.

Verlauf des Siebverfahrens von Euler für n = 100. Jede zusammengesetzte Zahl wird genau einmal gestrichen. Die Farbe einer gestrichenen Zahl entspricht der des kleinsten Primteiler der Zahl.

Im Sieb von Euler wird jede zusammengesetzte Zahl genau einmal gestrichen. Genauer gilt:

Satz (Eigenschaften des Siebs von Euler)

Für jede Grenze n gilt für das Siebverfahren von Euler:

(1)	Im Durchlauf k wird die k-te Primzahl p_k des Intervalls { 2, …, n } markiert.

(2)	Im Durchlauf k werden genau die zusammengesetzten Zahlen des Intervalls { 2, …, n } gestrichen, deren kleinster Primteiler p_k ist.

Der Beweis wird durch Induktion nach k geführt. Aus dem Satz folgt, dass genau diejenigen zusammengesetzten Zahlen die ersten k Durchläufe überleben, die nicht durch eine der ersten k Primzahlen teilbar sind.

Die folgende Tabelle gibt einen Eindruck von der Effizienz der drei Siebe. Wir zählen, wie oft Zahlen eines Intervalls { 2, …, n } während der Durchführung des Verfahrens insgesamt gestrichen werden.

n	Eratosthenes (lang)	Eratosthenes (kurz)	Euler
10	7	5	5
100	146	104	74
1000	1958	1411	831
10⁴	23071	16981	8770
10⁵	256808	193078	90407
10⁶	2775210	2122048	921501
10⁷	29465738	22850051	9335420

Anzahl der Streichungen der drei Siebverfahren

n	Eratosthenes (lang)	Eratosthenes (kurz)	Euler
10	0,7	0,5	0,5
10	1,46	1,04	0,74
10	1,96	1,41	0,83
10	2,31	1,70	0,88
10	2,57	1,93	0,90
10	2,78	2,12	0,92
10	2,95	2,28	0,93

Anzahl der Streichungen geteilt durch die Intervall-Länge (gerundet)