Sieb von Atkin

Das Sieb v​on Atkin i​st ein schneller, moderner Algorithmus z​ur Bestimmung a​ller Primzahlen b​is zu e​iner vorgegebenen Grenze. Es i​st eine optimierte Version d​es antiken Sieb d​es Eratosthenes: Das Atkinsieb leistet einige Vorarbeit u​nd streicht d​ann alle Vielfachen v​on Primzahlquadraten. Es w​urde von A. O. L. Atkin u​nd 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 a​lle Zahlen, d​ie durch zwei, d​rei 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 ${\displaystyle {\mathcal {O}}\left(N\right)}$ und einen Speicherbedarf von ${\displaystyle {\mathcal {O}}\left(N\right)}$ Bits.

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

Dabei ist ${\displaystyle {\mathcal {O}}}$ das Landau-Symbol und ${\displaystyle 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