Das Sieb von Atkin ist ein modernes und schnelles Verfahren (Algorithmus) zur Bestimmung von Primzahlen. Es beruht auf dem wohl bekanntesten Verfahren zur Primzahlbestimmung – dem Sieb des Eratosthenes. Auf dieser Seite könnt ihr euch ansehen, wie das Verfahren funktioniert. Diese Implementierung berechnet euch Primzahlen bis zu einer Obergrenze von 1 Million. Außerdem könnt ihr euch den hier eingesetzen (Javascript-) Code ansehen oder downloaden.
Sieb von Atkin
Das Sieb von Atkin ist eine optimierte Version des Sieb des Eratosthenes und wurde von A. O. L. Atkin und Daniel J. Bernstein entwickelt. Seine genaue Wirkungsweise wird auf Wikipedia beschrieben. Außerdem findet man dort den Pseudocode, welcher sich leicht umsetzen lässt (vgl. dazu den hier abgedruckten Javascript-Code).
Algorithmus testen und Primzahlen berechnen lassen
Sieb von Atkin – Code zum Demonstrationsbeispiel auf dieser Seite
Der unten dargestellte Code ist eine voll funktionstüchtige HTML-Seite und arbeitet genau wie das Formular mitsamt Code auf dieser Seite. Es steht natürlich auch als ZIP-Datei zum download bereit.
Sieb von Atkin - Demonstration