Sieb des Atkin

Sieb des Atkin

Das Sieb des 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.

Inhaltsverzeichnis

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 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: 4x2 + y2 = Eintragszahl.
    • 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: 3x2 + y2 = Eintragszahl.
    • 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: 3x2 - y2 = Eintragszahl, 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 4x2 + y2 = 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 3x2 + y2 = 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 3x2 - y2 = 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 22, 32, und 52 überprüft.

Komplexitätstheorie

Das Sieb benötigt O(N/log log N) Operationen bei nur N1/2+o(1) Bits Speicherverbrauch. Das Sieb des Eratosthenes benötigt O(N1/2(log log N)/log N) Operationen und O(N) Bits.

Literatur

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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… …   Deutsch Wikipedia

  • Sieb des Eratosthenes — Das Sieb des Eratosthenes ist ein Algorithmus zur Bestimmung einer Liste oder Tabelle aller Primzahlen kleiner oder gleich einer vorgegebenen Zahl. Er ist nach dem griechischen Mathematiker Eratosthenes von Kyrene benannt. Allerdings hat… …   Deutsch Wikipedia

  • Netz des Eratosthenes — Das Sieb des Eratosthenes ist ein Algorithmus zur Bestimmung einer Liste oder Tabelle aller Primzahlen kleiner oder gleich einer vorgegebenen Zahl. Er ist nach dem griechischen Mathematiker Eratosthenes von Kyrene benannt. Inhaltsverzeichnis 1… …   Deutsch Wikipedia

  • Primzahlensieb — Das Sieb des Eratosthenes ist ein Algorithmus zur Bestimmung einer Liste oder Tabelle aller Primzahlen kleiner oder gleich einer vorgegebenen Zahl. Er ist nach dem griechischen Mathematiker Eratosthenes von Kyrene benannt. Inhaltsverzeichnis 1… …   Deutsch Wikipedia

  • Primzahltest — Ein Primzahltest ist ein mathematisches Verfahren, um festzustellen, ob eine gegebene Zahl eine Primzahl ist oder nicht. Inhaltsverzeichnis 1 Praktische Anwendung 2 Bekannte Primzahltest Verfahren 2.1 Probedivision …   Deutsch Wikipedia

  • Daniel J. Bernstein — Daniel Bernstein (2010) Daniel Julius Bernstein (* 29. Oktober 1971 in East Patchogue, Long Island, New York) ist deutsch amerikanischer Mathematiker (Algorithmische Zahlentheorie), Kryptologe, Programmierer und Professor an der …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”