109.192.137.31: keine ist hier als Singular zu verstehen, also ist statt sind.

2025-05-19T20:48:02Z

keine ist hier als Singular zu verstehen, also ist statt sind.

Neue Seite

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. O. 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:   4''x''² + ''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:   3''x''² + ''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:   3''x''² − ''y''² = ''n'', wobei   ''x'' > ''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 1. Diese Zahlen sind genau dann prim, wenn die Anzahl an Lösungen für   4''x''² + ''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   3''x''² + ''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   3''x''² − ''y''² = ''n''   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 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 kB), Math. Comp. 73 (2004), 1023–1030.

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

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

Sieb von Atkin - Versionsgeschichte

109.192.137.31: keine ist hier als Singular zu verstehen, also ist statt sind.