Sieb von Atkin

Das Sieb von Atkin ist ein schneller, moderner Algorithmus zur Bestimmung aller Primzahlen bis zu einer vorgegebenen Grenze. Es ist eine optimierte Version des antiken Sieb des Eratosthenes: Das Atkinsieb leistet einige Vorarbeit und streicht dann alle Vielfachen von Primzahlquadraten. Es wurde von A. O. L. Atkin und Daniel J. Bernstein entwickelt.

Algorithmus

• Alle Reste sind Modulo 60 Reste (der Rest nach einer Division durch 60 wird betrachtet).
• Alle Zahlen, auch x und y, sind positive ganze Zahlen.
• Im Folgenden bedeutet Invertieren eines Eintrags der Siebliste, dass dessen Markierung (prim oder nicht-prim) zum Gegenteil gewechselt wird.

1. Erstelle eine mit 2, 3 und 5 gefüllte Ergebnisliste.
2. Erstelle eine Siebliste mit einem Eintrag für jede positive ganze Zahl; alle Einträge dieser Liste werden am Anfang als nicht-prim markiert.
3. Für jeden Eintrag n in der Siebliste führe folgendes aus:
   • Falls der Eintrag eine Zahl mit Rest 1, 13, 17, 29, 37, 41, 49 oder 53 enthält, invertiere ihn für jede mögliche Lösung der Gleichung:   4x² + y² = n.
   • Falls der Eintrag eine Zahl mit Rest 7, 19, 31 oder 43 enthält, invertiere ihn für jede mögliche Lösung der Gleichung:   3x² + y² = n.
   • Falls der Eintrag eine Zahl mit Rest 11, 23, 47 oder 59 enthält, invertiere ihn für jede mögliche Lösung der Gleichung:   3x² − y² = n, wobei   x > y.
4. Beginne mit der niedrigsten Zahl in der Siebliste.
5. Nimm die nächste Zahl in der Siebliste, die immer noch als prim markiert ist.
6. Füge die Zahl in die Ergebnisliste ein.
7. Quadriere die Zahl und markiere alle Vielfachen von diesem Quadrat als nicht-prim.
8. Wiederhole die Schritte 5 bis 8.

Erklärung

Der Algorithmus ignoriert alle Zahlen, die durch zwei, drei oder fünf teilbar sind.

• Alle Zahlen mit Modulo 60 Rest 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56 oder 58 sind teilbar durch zwei und nicht prim.
• Alle Zahlen mit Modulo 60 Rest 3, 9, 15, 21, 27, 33, 39, 45, 51 oder 57 sind teilbar durch drei und nicht prim.
• Alle Zahlen mit Modulo 60 Rest 5, 25, 35 oder 55 sind teilbar durch 5 und nicht prim. Diese Reste werden alle ignoriert.
• Alle Zahlen mit Modulo 60 Rest 1, 13, 17, 29, 37, 41, 49 oder 53 haben einen Modulo 4 Rest von 1. Diese Zahlen sind genau dann prim, wenn die Anzahl an Lösungen für   4x² + y² = n   ungerade ist und die Zahl quadratfrei ist.
• Alle Zahlen mit Modulo 60 Rest 7, 19, 31 oder 43 haben einen Modulo 6 Rest von 1. Diese Zahlen sind genau dann prim, wenn die Anzahl an Lösungen für   3x² + y² = n   ungerade ist und die Zahl quadratfrei ist.
• Alle Zahlen mit Modulo 60 Rest 11, 23, 47 oder 59 haben einen Modulo 12 Rest von 11. Diese Zahlen sind genau dann prim, wenn die Anzahl an Lösungen für   3x² − y² = n   ungerade ist und die Zahl quadratfrei ist.
• Keine der potentiellen Primzahlen sind teilbar durch 2, 3 oder 5, also können sie nicht durch ihre Quadrate teilbar sein. Deshalb wird die Quadratfreiheit nicht bei 2², 3², und 5² überprüft.

Komplexität

Das Sieb von Atkin hat eine Laufzeitkomplexität von ${\mathcal {O}}\left(N\right)$ und einen Speicherbedarf von ${\mathcal {O}}\left(N\right)$ Bits.

Zum Vergleich: Das Sieb des Eratosthenes hat eine Laufzeitkomplexität von ${\mathcal {O}}(N\log \log N)$ und benötigt ${\mathcal {O}}\left(N\right)$ Bits.

Dabei ist ${\mathcal {O}}$ das Landau-Symbol und $N$ die Anzahl der zu untersuchenden Zahlen.

Literatur

• A. O. L. Atkin, D. J. Bernstein, Prime sieves using binary quadratic forms (PDF; 185 kB), (1999).
• A. O. L. Atkin, D. J. Bernstein, Prime sieves using binary quadratic forms (PDF; 170 kB), Math. Comp. 73 (2004), 1023–1030.

Weblinks

• Optimierte Implementierung des Siebes