Erathostenes

---

Das klassische Sieb

Erathostenes (ca.300v.Chr.), griechischer Mathematiker, erdachte ein Verfahren, um systematisch Primzahlen aus einer Liste der natürlichen Zahlen zu erzeugen. Anstatt jede einzelne natürliche Zahl einem aufwendigen Test mittels Divisionen zu unterziehen, wandte Erathostenes ein raffinierteres Verfahren an, das bezeichnenderweise auch als Sieb des Erathostenes in die Geschichte der Mathematik einging..

Ausgangssituation: Benötigt wird eine Liste der natürlichen Zahlen, beginnend mit 2. Die Länge der Liste gibt die Obergrenze vor, bis zu der Primzahlen ermittelt werden. Die Zahlen dieser Liste können ausgestrichen werden. Per Konvention wird vereinbart, daß gestrichene Zahlen zusammengesetzt sind.

Idee: Man nehme die erste, nicht-ausgestrichene Zahl p der Liste. Diese Zahl p ist prim. Man multipliziere p systematisch mit den natürlichen Zahlen beginnend ab 2 und streiche alle Produkte aus der Liste. Dieses Verfahren wird so oft angewendet, bis die gesamte Liste abgearbeitet wurde. Das Schöne an diesem Verfahren ist: Man braucht keine Multiplikationen. Es genügt völlig, zum Wert np erneut p zu addieren um den nächsten Kandidaten für das Streichen aus der Liste zu erhalten.

Beispiel: Ermittle die Primzahlen bis 20 (gestrichene Zahlen rot, Primzahlen grün):

Schritt	erste Zahl	Liste
Anfang	2	2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1	3	2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
2	5	2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
3	7	2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
4	11	2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Ich unterbreche das grause Spiel mit einem Gedankengang, der uns viel Arbeit erspart. Wer genau hinsieht, erkennt, daß ab Schritt 2 bereits alle Primzahlen < 20 ausgesiebt wurden. Das kann Zufall sein, kann aber auch tiefere Gründe haben. Wir erinnern uns: das Verfahren streicht alle Zahlen, die Vielfaches einer Primzahl sind. Es ist eine altbekannte Tatsache, daß zusammengesetzte Zahlen mindestens aus 2 Faktoren bestehen, und daß einer der Faktoren kleiner oder gleich der Wurzel aus dieser Zahl sein muß. Es genügt folglich, das Siebverfahren auf Werte bis zur Wurzel der größten Zahl der Liste anzuwenden, um alle Primzahlen der Liste auszusieben.
Wenden wir diese Erkenntnis auf das obige Beispiel an, so sehen wir, daß das Ergebnis aus Schritt 2 noch nicht zwingend alle Primzahlen ausgesiebt hat, da 3² = 9. Mit Schritt 3 allerdings können wir des Ergebnisses sicher sein, da 5² = 25.

Dieser Trick läßt sich nutzbringend ein zweitesmal anwenden, wenn wir die Strategie des Verfahrens überdenken. Angenommen, es seien die Primzahlen bis zu einer bestimmten Zahl p_n bereits ermittelt. Die nächste noch nicht gestrichene Zahl sein damit p_n+1. Die Arbeitsvorschrift verlangt, alle Vielfachen von p_n+1 aus der Liste zu streichen. Es ist jedoch müßig, dies für die Faktoren 2, 3, ... , p_n durchzuführen. Die zugehörigen Werte sind nämlich bereits in einem der früheren Durchgänge entfernt worden. Der erste Faktor, den wir sinnvoll verwenden sollten, ist p_n+1. Darüberhinaus können wir uns auf die Faktoren beschränken, die noch nicht gestrichen wurden. Warum das? Ganz einfach. Wenn ein Wert n₁ gestrichen wurde, dann sind auch zwangsweise alle Vielfachen dieses Wertes ebenfalls gestrichen.

Algorithmen

Die bisherigen Erkenntnisse wollen wir nutzen, um einen speicher- und zeitsparenden Algorithmus zu entwickeln, der das Sieb das Erathosthenes in einer Programmumsetzung durchführt. Zunächst noch eine Vorüberlegung.

Datenrepräsentation

Wenn wir eine große Tabelle erzeugen möchten (z.B. die Primzahlen bis 10⁷), dann wird die Frage der internen Datenrepräsentation akut. Speicher ist zwar billig, aber wenn es gelingt, eine kompakte Darstellung der Primzahlen zu finden, und diese auch in der Laufzeit zu nutzen, dann ist der Gewinn doppelt. Frage: wieviel Speicher benötigt eine Primzahl? Naiv die Antwort: bei der genannten Größenordnung wird man sich für eine long-Variable entscheiden, das sind 32Bit - die in der Regel schlecht genutzt werden. Für die Primzahlen bis 10⁷ bräuchten wir dazu p(10⁷) ´ 4Bytes » nKByte. Wenn wir bedenken, daß wir die Siebtechnik verwenden wollen, dann müssen wir aber auch einen Speicherbereich für die Liste der natürlichen Zahlen vorsehen (Datentyp bool), der die jeweiligen Stati (prim/zusammengesetzt) aufnehmen kann. Bool wird in internen Repäsentationen der üblichen Programmiersprachen durch ein Byte repräsentiert. Folglich sind für diese Verwaltungsinformation 10⁷Byte zu veranschlagen. Ich halte das für maßlos.

Geht es kompakter? Es geht. Die Liste der Primzahlen ist redundant, denn dieselbe Information ist auch in der Sieb-Liste enthalten. Wenn wir nicht die Fragen stellen wollen: "welches ist die n-te Primzahl?" oder "was ist p(n) mit n <10⁷", dann ist die Tabelle vorerst nicht nötig.

Die Sieb-Liste ist ebenfalls sehr verschwenderisch. Für ein Bit Information wird ein ganzes Byte vernichtet. Das ist allemal um einen Faktor 8 zuviel. Wir können aber noch kompakter speichern, wenn wir uns die natürlichen Zahlen etwas genauer ansehen. Es gibt zwei "Ausnahmeprimzahlen": 2 und 5. Bezogen auf die Dezimaldarstellung können wir sagen, daß gerade Zahlen und Zahlen, die durch 5 bzw. 10 teilbar sind, in der Liste stets gestrichen werden. Speichern erübrigt sich also. In der Dezimaldarstellung können Primzahlen nur die letzten Ziffern 1,3,7 oder 9 haben. Betrachten wir das Zahlenintervall von [k´20+1, k´20+20], k natürliche Zahl, und teilen jede noch relevante natürliche Zahl mod 20:

Jetzt kommt eine Frage zum Horizont: was fällt auf? Dumme Frage, die Reste sind gleich den Zahlenwerten. Damit kann man was anfangen! Offenbar gibt es 8 Reste, die wir betrachtet haben. Jeder der Zahlenwerte aus dem Intervall kann zusammengesetzt oder prim sein. Nun kommt uns zupaß, daß ein Byte aus genau 8 Bit besteht. Ein Byte kann folglich beim Siebverfahren die Information eines Intervalls der Länge 20 aufnehmen. Wieviele Bytes benötigen wir mit dieser Strategie zur Speicherung der Informationen im Sieb?

(10⁶/20)Bytes = 5´10⁵Bytes, also knapp 50Kbyte.

Für einen Faktor 20 lohnt sich schon ein wenig Denkarbeit. Überdies kommt die gewählte Repräsentation der Algorithmik entgegen - vorausgesetzt, wir investieren auch hier ein wenig Hirnschmalz.

Ein Siebprogramm

yyy

der Code für diese Algorithmik muß noch um die notwendige Infrastruktur zum Erzeugen einer geeigneten Speicherfläche angereichert wserden - und los geht's!

yyy