Nicht nur wie, sondern warum es funktioniert

Warum funktioniert das Sieb von Atkin? Wie es funktioniert ist schnell erklärt. Hier findest du eine verständliche mathematische Erklärung statt nur einer Beschreibung des Algorithmus.

Inhalt dieser Website

Anschauliche Herleitung der Gleichungen

Die Erklärung basiert auf einfachen Überlegungen zur Teilbarkeit und vermeidet unnötig komplexe zahlentheoretische Begriffe. Ziel ist es, die Funktionsweise auch ohne Spezial-Wissen nachvollziehbar zu machen.

Optimierte Variante des Atkin-Algorithmus

Durch eine gezielte Einschränkung des Suchraums für die Variablen x und y lässt sich die Anzahl der Berechnungen deutlich reduzieren. Die Auswirkungen auf die Laufzeit werden anhand von Beispielen und Vergleichen gezeigt.

Alternative Count-Version

Diese Variante zählt die Anzahl der Lösungen und entfernt quadratische Vielfache direkt. Dadurch eignet sie sich auch für segmentierte Berechnungen und spezielle Anwendungsfälle.

Python-Code zum Vergleich verschiedener Primzahlsiebe

Die Implementierungen sind bewusst einfach gehalten und dienen dazu, die Unterschiede zwischen den Verfahren nachvollziehbar zu machen.

Grundidee

Die klassische Umsetzung des Siebs berechnet zunächst viele mögliche Werte und filtert anschließend die ungültigen heraus.

Die hier vorgestellte Herangehensweise geht einen anderen Weg: Es werden gezielt nur die Werte erzeugt, die die Bedingungen bereits erfüllen.

Dadurch ergibt sich ein deutlich eingeschränkter Suchraum, der effizienter durchsucht werden kann.

Hinweise zum Code

Die bereitgestellten Python-Beispiele können in einer geeigneten Python-Umgebung ausgeführt und überprüft werden.

Sie sind so strukturiert, dass sie auch für Einsteiger gut lesbar bleiben.

Ziel der Seite

Diese Seite dient der verständlichen Erklärung eines mathematischen Algorithmus sowie der Darstellung möglicher Optimierungen.

Sie richtet sich an Leserinnen und Leser, die sich für Primzahlen und algorithmische Zusammenhänge interessieren.

—

Autorin: Brigitte Brandl