Dieses Script erstellt eine Primzahlenliste mithilfe des Siebverfahrens von Eratosthenes. Dies beruht darauf, daß alle echten Vielfache natürlicher Zahlen (das sind alle Vielfache größer als die Zahl selbst) keine Primzahlen sein können, da sie ja diese Zahl als Teiler haben.

Das Script geht in vier Schritten vor:

1. Zunächst wird eine Liste A möglicher Primteiler für den gewünschten Zahlenbereich erstellt. Wenn beispielsweise die Primzahlen zwischen 50000 und 60000 gesucht werden, können nur Teiler bis zur Wurzel der Obergrenze Ö60000 = 244,94..., also bis 244 auftreten, also {2, 3, 4, 5, ..., 244}.
2. In dieser Liste werden nacheinander alle echten Vielfachen von 2, also {4, 6, 8, ..., 244}, gestrichen, dann die verbliebenen echten Vielfachen von 3 {9, 15, 21, ..., 243}, von 5, von 7 – und so fort. Zahlen über Ö245 = 15,65... können nach Streichen aller kleineren Faktoren schon keine echten Vielfachen mehr haben. Dadurch geht dieser Vorgang auch bei hohen Bereichsgrenzen ziemlich schnell.
   A ist damit eine Liste möglicher Primfaktoren des gewählten Zahlenbereichs.
3. Nun wird eine Liste B möglicher Primzahlen im gewählten Bereich erstellt. Gerade Zahlen können hier schon ausgeschlossen werden. (Theoretisch natürlich auch die Vielfachen von 5, dadurch könnte aber der Schritt 4 nicht so ablaufen. Praktischerweise wird nämlich gar keine Liste der Zahlen selbst erstellt, sondern nur eine Blankoliste, in der im nächsten Schritt eingetragen wird, ob eine Zahl keine Primzahl ist. Man braucht dazu eine einfachen Zuordnung zwischen gemeinter Zahl und Listenindex. Dann benötigt man im Grunde nur ein Bit pro Zahl.)
4. Zuletzt streicht man in B nacheinander alle Vielfachen von A. Dies erfolgt über die Indizes der Liste, d.h. bei allen Elemente in B, die zu Vielfachen von Elementen aus A gehören, wird das Bit gesetzt, die übrigen Bits bleiben ungesetzt.

Schließlich sind in Liste B nur noch diejenigen Elemente unmarkiert, die zu Primzahlen gehören.

© Arndt Brünner, 26. 3. 2005
Version: 26. 3. 2005