Quelltext der Seite Sieb von Atkin

Das '''Sieb von Atkin''' ist ein schneller, moderner [[Algorithmus]] zur Bestimmung aller [[Primzahl|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.&nbsp;O.&nbsp;L. Atkin]] und [[Daniel J. Bernstein]] entwickelt.

== Algorithmus ==
* Alle Reste sind [[Modulo]]-60-Reste (der [[Division mit Rest|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.
# Erstelle eine mit 2, 3 und 5 gefüllte Ergebnisliste.
# Erstelle eine Siebliste mit einem Eintrag für jede positive ganze Zahl; alle Einträge dieser Liste werden am Anfang als nicht prim markiert.
# 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: &nbsp; 4''x''²&nbsp;+&nbsp;''y''²&nbsp;=&nbsp;''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: &nbsp; 3''x''²&nbsp;+&nbsp;''y''²&nbsp;=&nbsp;''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: &nbsp;  3''x''²&nbsp;−&nbsp;''y''²&nbsp;=&nbsp;''n'', wobei &nbsp; ''x''&nbsp;>&nbsp;''y''.
# Beginne mit der niedrigsten Zahl in der Siebliste.
# Nimm die nächste Zahl in der Siebliste, die immer noch als prim markiert ist.
# Füge die Zahl in die Ergebnisliste ein.
# Quadriere die Zahl und markiere alle Vielfachen von diesem Quadrat als nicht prim.
# 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&nbsp;1. Diese Zahlen sind genau dann prim, wenn die Anzahl an Lösungen für &nbsp; 4''x''²&nbsp;+&nbsp;''y''²&nbsp;=&nbsp;''n'' &nbsp; 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 &nbsp; 3''x''²&nbsp;+&nbsp;''y''²&nbsp;=&nbsp;''n'' &nbsp; ungerade ist und die Zahl [[quadratfrei]] ist.
* Alle Zahlen mit Modulo 60 Rest 11, 23, 47 oder 59 haben einen Modulo 12 Rest von&nbsp;11. Diese Zahlen sind genau dann prim, wenn die Anzahl an Lösungen für &nbsp; 3''x''²&nbsp;−&nbsp;''y''²&nbsp;=&nbsp;''n'' &nbsp; ungerade ist und die Zahl [[quadratfrei]] ist.
* Keine der potentiellen Primzahlen ist 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 <math>\mathcal{O}\left(N\right)</math> und einen  Speicherbedarf von <math>\mathcal{O}\left(N\right)</math> Bits.

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

Dabei ist
<math>\mathcal{O}</math> das [[Landau-Symbol]] und 
<math>N</math> die Anzahl der zu untersuchenden Zahlen.

== Literatur ==
* A. O. L. Atkin, D. J. Bernstein, [http://cr.yp.to/papers/primesieves-19990826.pdf ''Prime sieves using binary quadratic forms''] (PDF; 185&nbsp;kB), (1999).
* A. O. L. Atkin, D. J. Bernstein, [http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf ''Prime sieves using binary quadratic forms''] (PDF; 170&nbsp;kB), Math. Comp. 73 (2004), 1023–1030.

== Weblinks ==
* [http://cr.yp.to/primegen.html Optimierte Implementierung des Siebes]

[[Kategorie:Primzahl]]
[[Kategorie:Zahlentheoretischer Algorithmus]]