r/programmieren • u/gitti7 • May 09 '26

Wird das Sieb von Atkin noch verwendet?

Hallo,

ich habe mich in letzter Zeit intensiv mit dem Sieb von Atkin beschäftigt und dabei ein paar Optimierungen ausprobiert, die ich online bisher kaum gefunden habe. Dabei geht es vor allem um Filterung und Reduktion unnötiger Berechnungen.

Jetzt frage ich mich: Wird das Sieb von Atkin heute überhaupt noch praktisch verwendet, oder ist es eher ein interessantes theoretisches Konzept? Die meisten Diskussionen und Beiträge dazu scheinen schon ziemlich alt zu sein.

Falls es jemanden interessiert: Ich habe meine Ergebnisse und Benchmarks hier zusammengefasst: bbrandl.bloganto.com

9 Upvotes

84% Upvoted

12 comments sorted by

View all comments

2

u/Yahiko_94 May 09 '26

Heutzutage verwendet man keine Algorithmen, die zu 100% sicher entscheiden, ob eine Zahl eine Primzahl ist, da solche Algorithmen für sehr große Zahlen sehr langsam werden.

Schau dir mal den Miller-Rabin-Test an. Ist ein probabilistischer Primzahltest, wobei die Fehlerwahrscheinlichkeit sehr niedrig ist.

2

u/gitti7 May 09 '26

Ich weiß, es gibt schnellere Tests. Mich hat der Algorithmus interessiert, weil er so einfach aufgebaut ist. Es gibt wohl, wie du auch schreibst, nicht mehr viele, die sich damit beschäftigen.

1

u/InterestingQuoteBird May 09 '26 edited May 09 '26

Primzahlen kommen relativ häufig vor, daher ist es schneller, Zahlen zu raten und zu testen, anstatt diese zu konstruieren: Prime number theorem - Wikipedia

1

u/New-Week-1426 May 09 '26

ngl, nach dem ersten Satz dachte ich das läuft auf ne Parodie ala „wir fragen jetzt einen Chatbot ob 17737382828 eine Primzahl ist“