Sieb des Eratosthenes

Das Sieb des Eratosthenes ist ein Algorithmus zur Bestimmung von Primzahlen. Er ist nach dem griechischen Mathematiker Eratosthenes von Kyrene benannt, dem dieses Verfahren bekannt gewesen sein soll. Der Algorithmus beruht darauf, dass in einem begrenzten Feld von natürlichen Zahlen die Primzahlen "ausgesiebt" werden. Die Vielfachen der unteren Primzahlen, beginnend mit 2, 3, 5 usw., werden markiert; die unmarkierten Zahlen, die übrig bleiben, sind prim.

Beschreibung

Das Sieb des Eratosthenes kann wie folgt beschrieben werden:

Es sollen die Primzahlen zwischen 2 (der ersten Primzahl) und einem Maximum m (im Beispiel: m=62) ermittelt werden.

1. Zunächst wird das Zahlenfeld initialisiert. Alle Zahlen zwischen 2 und m sind unmarkiert:

     2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
 61 62 ...

2. Die Variable n ist die jeweils zu bearbeitende Zahl. Sie wird auf 2 initialisiert.

 n = 2

3. Alle Vielfachen von n im Zahlenfeld werden gestrichen:

     2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
 61 62 ...

4. n wird auf die nächste unmarkierte Zahl gesetzt.

Zunächst ist also n = 3

5. Schritte 3 und 4 werden solange wiederholt, bis n größer als ${\sqrt {m}}$ ist.
Also werden als nächstes die (noch vorhandenen) Vielfachen von 3 gestrichen:

     2 3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
 61 62 ...

... danach die verbliebenen Vielfachen von 5:

     2 3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
 61 62 ... 

... danach restlichen die Vielfachen von 7:

     2 3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24  25 26 27 28 29 30 
 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
 61 62 ...  

... und so weiter.

Die übrig gebliebenen, fett gedruckten Zahlen sind die gesuchten Primzahlen.

Der Prozess kann bei der Wurzel aus m abbrechen (${\sqrt {62}}\approx 7,9$, die letzte zu bearbeitende Zahl ist also die n = 7), weil alle Produkte aus n und kleineren Primzahlen bereits markiert sind, und alle Produkte aus n und größeren Zahlen außerhalb des Feldes liegen.

Das Ergebnis ist dann:

     2 3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24  25 26 27 28 29 30 
 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
 61 62 ...  

In Schritt 3 können die Produkte aus n und kleineren Zahlen übersprungen werden, weil sie schon markiert sind. Man beginnt daher, um Zeit zu sparen, mit $n^{2}$.

Demonstration

Die Animation zeigt, wie die Primzahlen zwischen 2 und 120 ermittelt werden. Erst werden alle Vielfache von 2 markiert (rot), dann alle Vielfache von 3 (grün), 5 (blau) und 7 (gelb). Die Markierungen werden jeweils mit dem Quadrat der Primzahl begonnen, da kleinere Vielfache mindestens einen kleineren Primfaktor besitzen und daher bereits markiert sind. Da ab $11^{2}=121$ der Wertebereich überschritten wird, können alle unmarkierten Plätze als Primzahlen (lila) markiert werden.

Implementation

Eine beispielhafte Implementation des Algorithmus ist unter Primzahltest zu finden.

Literatur

• Hans Magnus Enzensberger, Der Zahlenteufel, ISBN 3-446-18900-9

Weblinks

• http://www.primzahlen.de/files/referent/kw/sieb.htm Windows-Programm mit Quelltext in C++
• http://www.madeasy.de/2/prgsieb.htm Primzahlsieb in Visual Basic
• http://www.faust.fr.bw.schule.de/mhb/eratosib.htm Interaktive Animation (erfordert JavaScript)
• Das Sieb des Eratosthenes erläutert