Sieb von Atkin

Das x und das y, das bei der Beschreibung des Siebs von Atkin verwendet wird, sind beliebige, positive, ganze Zahlen, die dazu verwendet werden, eine Bedingung für eine Zahl, die es zu erfüllen gilt, mathematisch zu formulieren.

So heißt es z.B., dass eine Zahl n, die nach dem Dividieren durch 60 den Rest 49 ergibt (Bsp: n=109), folgendes gelten muss:

Die Anzahl der Lösungen für die Gleichung ${\displaystyle \mathrm{n<mspace\; width="0.12em"></mspace>}={\mathrm{x<mspace\; width="0.12em"></mspace>}}^2+{\mathrm{y<mspace\; width="0.12em"></mspace>}}^2}$ muss ungerade sein, damit n eine Primzahl ist.

Auf der Suche nach Lösungen für die Gleichung, sei es hier jetzt im Beispiel ${\displaystyle 109={\mathrm{x<mspace\; width="0.12em"></mspace>}}^2+{\mathrm{y<mspace\; width="0.12em"></mspace>}}^2}$, muss man alle mögliche Werte für x und y durchprobieren, um alle mögliche Lösungen der Gleichung zu finden. Nach Ausprobieren findet man heraus, dass x=3 und y=10 die einzige Lösung für diese Gleichung ist. (Die Lösung x=10 und y=3 wird hierbei als äquivalent betrachtet.) Die Folge daraus ist, dass die Zahl 109 eine Primzahl ist.

x und y sind also allgemeine Variablen für Zahlen, die man nur durch ausprobieren genau bestimmen kann. Da dies ein Computeralgorithmus ist, ist der Zeitaufwand hier auch relativ gering.

Eine graphische Ablaufdarstellung von diesem Algorithmus kenne ich leider nicht.