Primzahlen-Test nach Atkin

618 Aufrufe

PDF an Freunde weiterleiten:

Ihre IP-Adresse wird aus Sicherheitsgründen gespeichert um kriminelle Aktivitäten und unerlaubten Spam zu unterbinden. Leiten Sie nur E-Mails weiter, wo der Empfänger mit dem Versand auch einverstanden ist.

1 
 
Primzahlen-Test                                                                          von Brigitte Brandl 
Ist der Rest (mod 24) einer beliebigen ganzen Zahl (P) farbig markiert, dann ist die dazugehörige 
Gleichung geeignet um zu berechnen, ob P eine Primzahl ist. Ist der Rest (mod 24) nirgendwo farbig 
markiert, dann ist P in jedem Fall durch 2 oder 3 teilbar.  
 
Primzahlkriterien 
Eine ganze Zahl P ist Primzahl, wenn im Rahmen der jeweils angegebenen Verhältnisse  
;    die geeignete Gleichung (d.h. P (mod 24) ist auffindbar) genau EINE ganzzahlige Lösung hat 
;    x bzw. y in dieser Lösung ungleich Null ist (andernfalls ist by2 bzw. ax2 = P) 
;    x und y in dieser Lösung keinen gemeinsamen Teiler haben (andernfalls teilt sein Quadrat P) 
;    P nicht durch 2, 3, oder 6 teilbar ist (dies trifft auf 1, 5, 7, 11, 13, 17, 19 und 23 (mod 24) zu) 
Primzahlen-Test 
1. Berechne für eine beliebige Zahl P den Rest (mod 24) und wähle eine geeignete Gleichung. 
2. Berechne das größte erlaubte x. Bsp.: P = 2x2 ʹ 3y2: x =ABRUNDEN((3P/2)0,5)  
3. Setze P und x in die Gleichung ein und suche mit absteigendem x nach y. Bsp.: y =((2x2-P)/3)0,5 
4. Ist eine ganzzahlige Lösung gefunden, prüfe x und y nach Primzahlkriterien.  
Beende den Test, wenn mehr als eine Lösung gefunden oder x bzw. y = Null ist. 
Für Gleichungen mit positivem Rechenzeichen stoppe den Test sobald y größer ist als x, und suche 
dann mit aufsteigenden, ganzzahligen y nach x. Das spart Ressourcen. 
Primzahlenliste für einen beliebigen Zahlenraum (frei nach Atkin) 
1. Wähle jeweils eine geeignete Gleichung für alle 8 P (1, 5, 7, 11, 13, 17, 19 und 23) und führe 
für jede Gleichung folgendes aus: 
2. Berechne das größte erlaubte x für den größten Eintrag in der Primzahlenliste und das 
kleinste erlaubte x für den kleinsten Eintrag mit y = 0 (oder x = Null in positiven Gleichungen). 
3. Berechne alle P dazwischen mit allen möglichen Kombinationen von x und y.                         
Notiere x, y und P gemeinsam zeilenweise in einer Liste. 
4. Lösche alle Zeilen, für die die Primzahlkriterien (für x, y oder P) nicht erfüllt sind. 
Für eine Primzahlenliste müssen x und y genauer definiert werden. Vergl. die Tabellen auf Seite 
2. Man kann die Liste auch für mehrere der 8 P gleichzeitig erstellen, wenn sie aus der gleichen 
Gleichung kommen. 
Ein Vorteil ist, dass die Liste nicht mit 2 beginnen muss. Ein Nachteil ist, dass jede endgültige 
Lösung auf gemeinsame Teiler in x und y überprüft werden muss. Soll die Liste mit 2 beginnen, 
kann man anstatt nach gemeinsamen Teilern zu suchen, wie beim Sieb von Atkin alle Vielfachen 
von Quadraten streichen.  
ax2by2
1.1x2+3y2=1713
2 
 
Tabellen für x und y 
x aus der Gleichung entspricht den Zeilenüberschriften und y den Spaltenüberschriften. x und y sind 
Reste (mod 12), manchmal geht auch (mod 2), (mod 4) oder (mod 6). Alle berechneten P sind Reste 
(mod 24). Die Gleichungen 5/9, 6/8 sowie 11/12 liefern jeweils gleich viele Lösungen für ein P. 
 
1x2+3y2=
3 
 
Erklärung 
Zu jeder der Tabellen gehört eine Menge von vier Teilern (mod 24). Diese sind jeweils daneben farbig 
markiert. Wenn sich P nur als Produkt aus Elementen einer Teilermenge darstellen lässt, (hier teilt 
auch 1) dann gibt es ganzzahlige Lösungen. Bsp.: für 1729 gibt es in Gleichung 1 vier ganzzahlige 
Lösungen. Eine für 7*(13*19), eine für 13*(7*19), eine für 19*(7*13) und eine für 1*1729. Eine 
Lösung zeigt nicht die Teiler, sondern nur die Teilbarkeit.  
Ist ein fremder Teiler im Spiel (ein Teiler (mod 24), der nicht farbig markiert ist), dann gibt es keine 
Lösung. Bsp.: 5*7*13 = 455 kann in keiner der 13 Gleichungen ganzzahlig gelöst werden. Im Quadrat 
kann auch ein fremder Teiler zu EINER ganzzahligen Lösung führen. Dann haben x und y entweder 
gemeinsame Teiler oder x bzw. y = Null. Gibt es weitere Teiler aus der zugehörigen Teilermenge, 
dann ist die Anzahl der Lösungen ungerade. Im grauen Bereich der Tabellen haben x und y immer 
gemeinsame Teiler oder x bzw. y = Null. Hier haben alle P mindestens einen quadratischen Teiler. 
Die grün markierten Felder beziehen sich auf die Teilermenge (mod 24) in den Feldern darüber. Ist 1 
markiert, dann wird das 1, 4, 9, 16, 36, ͙ĨĂĐŚĞ, ist 2 markiert, dann wird das 2, 8, 18, 32, 72, ͙ĨĂĐŚĞ, 
ist 3 markiert, dann wird das 3, 12, 27, 48, 108, ͙ĨĂĐŚĞ͕ŝƐƚϲŵĂƌŬŝĞƌƚ, dann wird das 6, 24, 54, 96, 
216, ͙ĨĂĐŚĞĚĞƌŵĂƌŬŝĞƌƚĞŶdĞŝůĞƌ(mod 24) oberhalb ganzzahlig gelöst (das 1, 2, 3, oder 6fache von 
Quadraten, die nur durch 2 oder 3 teilbar sind). Auch für durch 2 oder 3 teilbare P gilt: Gibt es fremde 
Teiler, dann gibt es keine ganzzahlige Lösung. Ausnahme: Quadratische fremde Teiler. 
Es gibt jeweils genau gleich viele oder mehr (niemals weniger) Lösungen für ĚĂƐϭ͕ϰ͕͙ĨĂĐŚĞeines P 
(wenn grün markiert). Das gleiche gilt für das 2, 8, ͙fache, 3, 12, ͙fache und 6, 24͕͙fache eines P. 
Das 1, 2, 3 und 6fache einer Primzahl führt zu genau EINER ganzzahligen Lösung (wenn grün 
markiert). Ausnahme Gleichung 10: Für das 3fache und 6fache gibt es hier mehr als eine Lösung.  
Die Anzahl der Lösungen ist demnach nur für Primzahlen (genau EINE Lösung) aussagekräftig. 
Dies lässt sich einfach nachprüfen: Erstelle eine Tabelle für alle P mit x und y aus einer Gleichung (z.B. 
bis 10.000). Berechne daneben den Rest (mod 24) und sortiere P nach diesem. Schneide alle Zeilen 
mit Rest (mod 24) = 1, 5, 7, 11, 13, 17, 19 oder 23 aus und schreibe sie jeweils in eine eigene Tabelle.  
Sortiere alle übrigen P wieder nach Größe, dividiere sie durch 2 und berechne für die Ergebnisse den 
Rest (mod 24). Sortiere nach Diesem. Schneide die 8 P (wie oben) aus und schreibe sie neben obige P 
mit gleichem Rest (mod 24). Wiederhole dies mit 3, 4, 6, 8, 9... Die bedingte Formatierung ͣDoppelte 
Werte͞Ĩƺƌdie berechneten P macht 
4 
 
Grundlagen für die Verhältnisse x : y 
In den folgenden Tabellen sind die jeweils ersten beiden Lösungen für die jeweils ersten 10 
Primzahlen pro Gleichung berechnet. Jeweils daneben steht der Rest (mod 24) der Primzahl. Vergl. 
Gleichung 2x2 ʹ 1y2 = P: Bei 2 * 32 - 12 = 17 ist x noch größer als y. Bei 2 * 72 ʹ 92 = 17 ist x schon 
kleiner als y. Nur die jeweils Erste der beiden Lösungen liegt im Rahmen der angegebenen 
Verhältnisse. Die angegebenen Verhältnisse hängen hauptsächlich von den Lösungen für Primzahlen 
ab. Positive Gleichungen haben nur eine Lösung für Primzahlen und sind daher hier nicht angeführt. 
 
  
1x2 - 3y23x2 - 1y22x2 - 3y23x2 - 2y21x2 - 6y26x2 - 1y21x2 - 2y21x2 - 2y22x2 - 1y22x2 - 1y2
x => 3yx => yx => 1,5yx => yx => 3yx => 0,5yx => 2yx => 2yx => yx => y
xyxyxyxyxyxyxyxyxyxy
1011211111215511111011115510115217171111311717
21113411114355911115211375532117417175711791717
1037315459114129551731134731352959273172411775731534117
114731675911141129521257311767315112951912731138411711137319114117
101971658311855357597111297131535136971114891771971738917
17897178831110753515179713112971133153515897117108917192597115198917
14119316110711831015951931174193157101515419311121131711719319711317
25121931111610711221710152529193137141931112510152918193125161131719231931131511317
1742411741311114914959124112582411511495211024111341371711124119513717
2292411101313111161114954149241129102411235514952312241123141371731412411172113717
194313198179111031735115313123631317111735218313119823317135313111323317
2611
5 
 
Lösungen für durch 2 oder 3 teilbare Zahlen 
Die grün markierten Felder entsprechen dem 1, 2, 3 oder 6fachen von Quadraten, die nur durch 2 
oder 3 teilbar sind. (Ausnahme: 1) Die Listen könnten endlos verlängert werden. Ist 1 grün markiert, 
dann wird das 1fache der markierten Teiler ganzzahlig gelöst usw. 
 
Vergleicht man alle grünen Markierungen miteinander, dann wird sichtbar, dass fast alle n-fachen 
von allen sieben Teilermengen (mod 24) ganzzahlig gelöst werden können, wenn kein fremder Teiler 
(ein Teiler, der nicht farbig markiert ist) im Spiel ist. Ausnahmen in vier Gleichungen. Fremde Teiler 
können nur im Quadrat (dieses ergibt 1 (mod 24)) zu einer ganzzahligen Lösung führen. 
a und b aus den Gleichungen (1, 2, 3, oder 6) kommen in allen möglichen Kombinationen vor, die 
nicht in jedem Fall eine durch 2 oder 3 teilbare Zahl ergeben.  
2x2 + 6y2 löst die n-fachen, die 1x2 + 3y2 nicht löst. 
3x2 ʹ 6y2 löst die n-fachen, die 1x2 ʹ 2y2 nicht löst. 
6x2 ʹ 3y2 löst die n-fachen, die 2x2 ʹ 1y2 nicht löst.  
3x2 + 3y2 löst die n-fachen, die 1x2 + 1y2 nicht löst. 
Man findet die fehlenden n-fachen auch, indem man die Gleichungen mit 2 bzw. 3 multipliziert. 
  
Teiler (mod 24)Das grün markierte n-fache der markierten Teiler führt zu einer Lösung
x < = > y1x2+3y217131914916362818327231227481086245496216
(mal 2)511172314916362818327231227481086245496216
x => 3y1x2-3y217131914916362818327231227481086245496216
511172314916362818327231227481086245496216
x => y3x2-1y217131914916362818327231227481086245496216
511172314916362818327231227481086245496216
x < = > y
6 
 
 
7 
 
Die größte sinnvolle Aufteilung von x und y 
Auch in den Tabellen auf Seite 6 entspricht x den Zeilenüberschriften und y den Spaltenüberschriften. 
In einigen Gleichungen sind x und y vertauscht, damit alle Tabellen auf eine Seite passen. Alle P sind 
Reste (mod 288) und können theoretisch eine Primzahl sein. Ausnahme: In den beiden grauen 
Feldern, hier gibt es immer gemeinsame Teiler in x und y oder x bzw. y = Null. 
Für jedes P (mod 24) gibt es 12 P (mod 288). x und y, die das gleiche P (mod 288) ergeben, sind in 
einer Zeile/Spalte zusammengefasst. Ein P (mod 288) kann also mit jeder Kombination aus x 
(nebeneinander) und y (übereinander) gelöst werden. x gilt für alle Tabellen nebeneinander.  Alles ist 
weitestgehend komprimiert. 
Drei Tabellen sind mit einer zweiten Tabelle verbunden und sind als eine Tabelle zu werten. Vergl. 
mit den Tabellen auf Seite 2.  
Für x bzw. y kann es verschiedene (mod n) geben, diese können aber zu einem gemeinsamen (mod n) 
aufaddiert werden. Alle x in einer Zeile und y in einer Spalte sind von oben und von unten gleich, sie 
können zum zugehörigen (mod n) addiert oder von diesem subtrahiert werden. Man kann also beim 
kleinsten oder größten x bzw. y beginnen. Das gilt auch für x und y auf Seite 2. 
Wenn man alle x für ein einzelnes P sucht, ist manchmal auch ein kleineres (mod n) möglich: Für         
P = 17 (mod 288) in Gleichung 1x2 + 1y2 entsprechen alle möglichen x (mod 144) den Resten                
1, 7, 17, 23 (mod 24). Alle möglichen y (mod 72) entsprechen den Resten 4, 8 (mod 12). Das sollte 
immer geprüft werden.  
In Gleichung 1x2 + 1y2 kann man x und y gleichzeitig in einem Arbeitsschritt berechnen und enden, 
sobald x <= y ist. Für P = 17 (mod 288) ist dann x = 1, 4, 7, 8, 16, 17, 20, 23 (mod 24). 
Rechenbeispiel  
P = 345.617; Rest 17 (mod 288); Gleichung 1x2 + 1y2 
1. Berechne das größte erlaubte x und runde ab. ABRUNDEN(345.6170,5) = 587 
2. Berechne für das Ergebnis (mod n). 587 = 11 (mod 24) 
3. Suche das nächstkleinere x aus der Tabelle und vergleiche es mit dem Ergebnis. 11 ʹ 8 = 3 
4. Subtrahiere die Differenz. Das ist das erste x für die Gleichung. 587 ʹ 3 = 584 (= 8 (mod 24)) 
5. Für die nächsten x subtrahiere (mod n) vom Ergebnis sooft, bis dass das kleinste erlaubte x 
erreicht ist. 584 ʹ 24 = nächstes x usw. 
 
6. Suche das nächstkleinere x aus der Tabelle und subtrahiere die Differenz.  
584 ʹ 1 = 583 (= 7 (mod 24) Das ist das nächste x für die Gleichung. 
7. Wiederhole Schritt 5 mit diesem x. 
8. Wiederhole die Schritte 6 und 7 für die restlichen Reste (mod n). Jeder Rest (mod 24) muss 
nur einmal berechnet werden. 
Beachte, dass Reste (mod 24) gesucht werden: 577 = 1 (mod 24);   577 ʹ 2 = 575 = 23 (mod 24) 
 
 
  
Eingestellt über www.PDF-ins-Internet.de - Haftung für Inhalt und Inhaber aller Rechte ist der Puplisher
Kontaktdaten und Anbieterkennung des Puplishers/Autors entnehmen Sie bitte dem PDF-Archives auf www.PDF-ins-Internet.de.
8 
 
Durch fünf teilbare P anzeigen 
Um alle durch 5 teilbaren P anzuzeigen, wird mit P (mod 120) gerechnet. P (mod 60) ist nicht 
geeignet, weil 60 nicht durch 24 teilbar ist. Vergl. Sieb von Atkin auf Wikipedia: Mit P (mod 60) kann 
nicht unterschieden werden zwischen 1/13, 5/17, 7/19 oder 11/23 (mod 24). Mit P (mod 120) kann 
man aus allen Gleichungen frei wählen und man muss nur die Zahlen 1, 7, 11, 13, 17, 19, 23 und 29 
(mod 30) in die Siebliste schreiben. 
 
Für jedes P (mod 24) gibt es hier 5 P (mod 120), diese sind jeweils gemeinsam in einem 3*3-Kästchen 
farbig markiert. Die Positionen der durch 5 teilbaren P zeigen deutlich, ob 5 zur Teilermenge gehört 
oder nicht. Wenn 5 nicht dazu gehört, sind alle P an den grau markierten Positionen durch 25 teilbar. 
x und y haben hier immer einen gemeinsamen Teiler oder x bzw. y = Null.  
Wenn alle x bzw. y gerade sind, kann man statt n2 auch 4m2 
schreiben. Darum liefern die Gleichungen 1x2 + 1y2 = P und  
1x2 + 4y2 = P die gleichen nicht durch 2 oder 3 teilbaren P  
mit anderen y.  
In Gleichung 10 kann P = 17 (mod 24) mit 9x2 + 8y2 = P  
berechnet werden usw. In negativen Gleichungen muss das 
Verhältnis x : y an das Verhältnis ax2 : by2 : P angepasst werden. 
Nimm ein P aus der Tabelle 1x2 ʹ 3y2 und addiere es zum P aus der Tabelle 3y2 ʹ 1x2 an der gleichen 
Position. Das Ergebnis ist immer 120. Vertauscht man ax2 und by2 in negativen Gleichungen, dann 
ergibt sich der gegenteilige Rest (mod 120). Dies funktioniert auch für alle negativen Gleichungen auf 
Seite 6. 
 
9 
 
Erstelle für a, b und (mod 24) absolute  
Bezüge und berechne (ax2) + (by2),  
dann kann jede Gleichung in derselben  
Tabelle gelöst werden. Formatiere mit  
ĚĞƌďĞĚŝŶŐƚĞŶ&ŽƌŵĂƚŝĞƌƵŶŐͣEƵƌĞůůĞŶ 
ĨŽƌŵĂƚŝĞƌĞŶ͕ĚŝĞĞŶƚŚĂůƚĞŶ͞ϭ͕ϱ͕ϳ͕ϭϭ͕ 
13, 17, 19 und 23 jeweils mit einer  
eigenen Farbe. Das schafft Übersicht. 
Teiler zurückholen 
P wird mit (x + y)*(x ʹ y) berechnet. Dies wird umgeformt zu P = x2 ʹ y2. Berechne zuerst P0,5 (hier ist   
x = P0,5 und y = Null). Runde x auf und suche mit aufsteigendem x nach ganzzahligen y.  
Anm.: In einem rechtwinkeligen Dreieck sind die Seitenlängen der 13 Gleichungen Bruchzahlen (a0,5x, 
b0,5y und P0,5). Die Seitenquadrate sind ganzzahlig (ax2, by2 und P). Somit kann der Satz des 
Pythagoras auf diese ganzen Zahlen angewendet werden. Der direkte Bezug zu ganzzahligen Teilern 
geht jedoch verloren. a und b dürfen nur die Werte 1, 2, 3 oder 6 annehmen. Ein indirekter Bezug zu 
den beschriebenen Teilermengen (mod 24) bleibt dadurch erhalten: Gibt es eine ganzzahlige Lösung, 
dann kommen alle Teiler aus der zugehörigen Teilermenge (hier teilt auch 1) oder (und) aus dem 
Quadrat eines fremden Teilers. 
Nahe der Wurzel wächst der Abstand zum Durchschnitt (y) viel schneller als der Durchschnitt (x). 
Dadurch lassen sich mit der Gleichung (x2 ʹ P)0,5 = y größere Teiler bis zur Wurzel sehr schnell finden. 
Für die kleineren Teiler bleibt die Probedivision. 
Vergl. mit dem goldenen Schnitt (1,618033): P = 100; Verhältnis: x2 : P : y2 = 5 : 4 : 1 (125 : 100 : 25): 
(11,180332 ʹ 100)0,5 = 5; x + y = 16,18033 (größerer Faktor); x ʹ y = 6,18033 (kleinerer Faktor). Mit 
dieser Gleichung findet man zwei Teiler, die einen geraden Abstand zueinander haben. 
Auch hier lassen sich x und y mit Hilfe einer Tabelle eingrenzen. Vergl. die Tabellen auf Seite 10. Für x 
und y schreibe alle Zahlen von 0 bis 863 in einer Spalte untereinander. Berechne jeweils daneben das 
Quadrat. Berechne jeweils daneben für das Quadrat (mod 16), (mod 9), (mod 64) und (mod 27) und 
sortiere nach diesen Spalten in dieser Reihenfolge. Suche für alle Zahlen mit gleichen (mod n) ein 
kleinstes (mod n) ab dem sich die Reste wiederholen (Vergl. alle (mod n) auf Seite 10). 
Setze x und y in die Tabelle ein und berechne P (mod 24). Lösche alle Felder, die nicht die Lösungen 
1, 5, 7, 11, 13, 17, 19 oder 23 ergeben oder formatiere diese mit der bedingten Formatierung 
ͣ&ĂƌďƐĐĂůĞŶ͕͞ƵŵƐŝĞƐƉćƚĞƌǀŽŶĚƵƌĐŚϮŽĚĞƌϯƚĞŝůďĂƌĞŶWƵŶƚĞƌƐĐŚĞŝĚĞŶǌƵŬƂŶŶĞŶ͘Dann berechne 
P (mod 1728).  
x und y sind relativ zu allen Teilern von 1728 sortiert. Man kann daher anstatt (mod 1728) alle Teiler 
von 1728 einfügen. Für jedes P (mod 24) gibt es 72 P (mod 1728). Auch hier sind alle x in einer Zeile 
und alle y in einer Spalte von oben und von unten gleich. Man kann sie daher sowohl zu (mod n) 
addieren, als auch davon subtrahieren. Auf Seite 10 ergeben alle P in den unteren Tabellen den 
gegenteiligen Rest (mod 1728) von den oberen Tabellen. 
Um alle durch 5 teilbaren P anzuzeigen, schreibe alle Zahlen von 0 bis 4319 in einer Spalte 
untereinander. Berechne jeweils daneben das Quadrat. Berechne jeweils daneben für das Quadrat 
(mod 16), (mod 9), (mod 64), (mod 27
10

Eingestellt über www.PDF-ins-Internet.de - Haftung für Inhalt und Inhaber aller Rechte ist der Puplisher
Kontaktdaten und Anbieterkennung des Puplishers/Autors entnehmen Sie bitte dem PDF-Archives auf www.PDF-ins-Internet.de.
11 
 
Primzahlen-Sieb (frei nach Eratosthenes) 
Man braucht 3 Variablen mit folgenden Anfangswerten:  
 a = 6  für das Produkt aller Primzahlen in der Saveliste 
 b = 30   für das nächstgrößere Primzahlenprodukt 
 x = 500  kann manuell eingegeben werden. Die Liste soll alle Primzahlen bis 500 enthalten. 
und 2 Listen mit folgenden Einträgen: 
 Primzahlenliste: 5, 7 
 Saveliste: 2, 3 für alle Primfaktoren von a, diese werden aus der Primzahlenliste gelöscht 
und zum Schluss wieder eingefügt, wodurch die Primzahlenliste ohne Vielfache dieser 
Primfaktoren verlängert werden kann. 
Wenn b < x ist, dann gehe zu Schritt 1, sonst gehe zu Schritt 5. 
1. Solange, bis dass die Summe = b + 1 ist, addiere a nacheinander zu jedem Eintrag in der 
Primzahlenliste und schreibe die Summen jeweils an das Ende der Liste.  
2. Solange das Produkt < b ist, multipliziere den ersten Eintrag zuerst mit sich selbst, und dann 
mit den nachfolgenden Einträgen und lösche jedes Produkt aus der Primzahlenliste.  
3. Verschiebe den ersten Eintrag von der Primzahlenliste in die Saveliste. 
4. Berechne die Variablen neu:  
a = b Der Wert in a wird durch das nächstgrößere Primzahlenprodukt (b) ersetzt. 
b = a mal erster Eintrag aus der Primzahlenliste 
Wenn b < x ist, dann gehe zu Schritt 1, sonst gehe zu Schritt 5. 
5. Solange die Summe <= x ist, addiere a nacheinander zu den Einträgen in der Primzahlenliste 
und schreibe die Summen jeweils an das Ende der Liste. 
6. Solange das Produkt <= x ist multipliziere den ersten Eintrag zuerst mit sich selbst und dann 
mit den nachfolgenden Einträgen und lösche jedes Produkt aus der Primzahlenliste.  
7. Wiederhole Schritt 6 mit dem zweiten und den nachfolgenden Einträgen solange, bis kein 
Produkt mehr auffindbar ist. 
8. Importiere alle Einträge aus der Saveliste in die Primzahlenliste um diese zu vervollständigen. 
Gibt es einen größten Primzahlzwilling? 
Würde man alle bekannten Primzahlen miteinander multiplizieren, dann wäre das Produkt + 1 
wieder eine Primzahl oder durch eine noch unbekannte Primzahl teilbar. Das Gleiche gilt für das 
Produkt ʹ 1. Die Möglichkeit eines Primzahlzwillings ist also unendlich oft gegeben. 
Vergl. die ersten vier Schritte im Primzahlen-Sieb: Das Vielfache von 5 kann die Abstände zwischen 
ǌǁĞŝWƌŝŵǌĂŚůĞŶ;Ϯ͕ϰ͕ϲ͕ϴ͙ͿďŝƐǌƵŵWƌŝŵǌĂŚůĞŶƉƌŽĚƵŬƚϯϬŶŝĐŚƚĞůŝŵŝŶŝĞƌĞŶ͘Die Abstände 
wiederholen sich bis zum Primzahlenprodukt 210 (und darüber hinaus). Auch die Vielfachen von 7 
können keine Abstände komplett eliminieren, sie liegen zu weit auseinander. Also gelingt dies auch 
ŶŝĐŚƚĚĞŶsŝĞůĨĂĐŚĞŶǀŽŶϭϭ͕ϭϯ͕ϭϳ͙, wenn man das Sieb weiterführt. Ihre Vielfachen liegen noch 
weiter auseinander, sodass zwischen ihnen immer kleine Abstände erhalten bleiben. Nur der 
Abstand 1 (zwischen 2 und 3) kann sich nicht wiederholen. Es gibt also keinen größten Primzahl-
zwilling.  
123456789101112131415161718192021222324252627282930
313233343536373839404142434445464748495051525354555657585960
616263646566676869707172737475767778798081828384858687888990
919293949596979899100101102103104105106107108109110111112113114115116117118119120
121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150
151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180
181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210
211

Primzahlen-Test nach Atkin

PDF & Publisher Info