Home

Sieb des Eratosthenes

Um alle Primzahlen bis zu einer vorgegebenen Grenze N zu erhalten, benutzt man das Sieb des Eratosthenes. Es arbeitet folgendermaßen:

Eingabe: Schreibe die Zahlen von 2 bis N auf und setze M = 2.

  1. Streiche alle Vielfachen von M zwischen M*M und N.
  2. Erhöhe M auf den Wert der nächsten ungestrichenen Zahl. Wiederhole ab Schritt 1, solange M*M < N gilt.

Die nichtgestrichenen Zahlen sind jetzt genau die Primzahlen <= N.

Ein (unbegrenztes) Sieb des Eratosthenes

Hier ein kleines Java-Programm (compilierte Class-Datei und Quellcode) zum Sieb des Eratosthenes. Die Besonderheit ist, dass es nicht durch die Größe des Arbeitsspeichers begrenzt ist, sondern durch wiederholte Aufrufe beliebig weitersieben kann.

Beispielsweise werden durch den Aufruf

        java Eratosthenes primes.txt 10000

zunächst einmal die Zahlen bis 10000 durchsiebt und die Datei "primes.txt" angelegt. Der Aufruf

        java Eratosthenes primes.txt 100000000

verwendet die vorhandene "primes.txt" dann, um die nächsten 100 Millionen Zahlen zu testen.

Durch wiederholte Aufrufe gewinnt man immer neue Primzahlen hinzu. (Um etwas mehr Speicher für die Java-VM zu reservieren, verwendet man den Parameter -Xmx. So stehen dem Programm mit java -Xmx1000m Eratosthenes ... beispielsweise 1 GB RAM zur Verfügung.) Das kann man fortsetzen, bis der Festplattenplatz ausgeht, keine aufeinanderfolgenden zwei Primzahlen mehr in den Arbeitsspeicher passen oder das Universum verschwunden ist.

Hinweis: Das vorliegende Programm ist sehr knapp gehalten und in keiner Hinsicht auf besonders hohe Geschwindigkeit oder die Ausnutzung der Besonderheiten einer bestimmten Rechnerarchitektur optimiert (ist aber durchaus hinreichend schnell, um sich die Festplatte mit Primzahlen zu überfüllen ...) Es geht in erster Linie um eine Demonstration des "Weitersiebens".

Wer wirklich schnell viele Primzahlen ersieben möchte, sei auf das äußerst schnelle Programm "Ecprime" von Kim Walisch verwiesen (Programm und Quellcode finden sich in den Downloads zum Artikel "64-Bit-Werkstatt" aus c't 5/05, S. 118).

Zum Durchlaufen der Zahlen bis zur Grenze N = 10 Milliarden benötigt es auf einem durchschnittlichen Notebook nur wenige Sekunden (die Zeit für das Abspeichern der Primzahlen nicht eingerechnet), siebt bis zu einer theoretischen Grenze von etwa 10**19 und sprengt damit sicherlich jeden Rahmen, was Festplattenspeicher und Zeitbedarf angeht ...

Zuletzt geändert: 2010-01-13, Stefan Reiser (s.reiser@tu-bs.de)