der Primzahlen:
Eine Zahl ist prim, wenn sie nur durch 1 und durch sich selbst teilbar
ist. Beispiel: 7 ist eine Primzahl, weil sie nur durch 1 und 7 ohne Rest
teilbar ist. Ich definiere dementsprechend die Menge
der Primzahlen:
Mit der Prozedur summe_der_teiler, die dem 
entspricht, schreibe ich nun eine Funktion prim (s. Seite [*]).
EUKLID hat bewiesen, dass es unendlich viele Primzahlen gibt. TSCHEBYTSCHEW
bewies, dass zwischen x und einschliesslich 2x immer eine
Primzahl liegt, vorausgesetzt 
. GOLDBACH behauptete, eine Zahl 
ist immer aus zwei Primzahlen zusammengesetzt, doch niemand konnte das
bis jetzt beweisen. Hier muss x grösser als 2 sein.[+]
Bis jetzt ist nicht bekannt, wie man direkt testen kann, ob eine Zahl n prim ist. Die einzige Möglichkeit ist das Testen aller Zahlen unter n, ob sie Teiler von n sind, was bei grossen Zahlen sehr zeitaufwendig ist.
Mit dem Sieb des ERATOSTHENES kann man leicht alle Primzahlen bis zu einer bestimmten Grenze herausfinden. Zuerst schreibt man alle Zahlen bis zur gewünschten Grenze in einem Raster auf und streicht dann alle Vielfachen von 2, die 2 selbst bleibt aber stehen. Dann werden alle Vielfachen von 3 gestrichen, die durch 4 teilbaren sind schon im ersten Durchgang gestrichen worden. So verfährt man mit 5 usw. bis zur Obergrenze. Die dann übrigbleibenden Zahlen sind prim. Die Primzahlen zwischen 2 und 50 zeigt das folgende Raster:
Statt die Zahlen durchzustreichen, habe ich sie grau geschrieben.
Im Sieb des ERATOSTHENES habe ich die 1 bewusst weggelassen, denn auf
die Frage, ob die 1 eine Primzahl ist, habe ich in keinem Buch eine Antwort
gefunden.[+]
Einerseits heisst es in der Definition, dass eine Zahl keine anderen Teiler
ausser 1 und sich selbst hat. Nun ist 1 aber gleich der Zahl selbst, gilt
die Regel trotzdem? Man könnte die Definition auch so aufstellen,
dass eine Primzahl genau zwei Teiler hat. Dann wäre die 1 auf keinen
Fall in der Menge der Primzahlen enthalten. In meiner Menge
ist die 1 nicht enthalten, denn 
und 1 + 1 = 2 . Ob die 1 eine Primzahl ist, ist also scheinbar Definitionssache.
Dafür, dass 1 keine Primzahl ist, spricht, dass jede Zahl in Primfaktoren
zerlegt werden kann. Dabei wird die Zahl als Produkt von mehreren Primzahlen
geschrieben. Die Zuweisung zwischen der Zahl und ihren Primfaktoren ist
in beide Richtungen eindeutig, z.B. 
. Wenn jetzt aber die 1 auch eine Primzahl wäre, dann gäbe es
mehrere Multiplikationen mit dem Ergebnis 6: z.B. 
oder 
.
Primzahlzwillinge nennt man zwei Primzahlen, die die Differenz 2 haben,
z.B. 3 und 5, 5 und 7 etc. Mit Variablen ausgedrückt bedeutet das,
es gibt eine Zahl 
und eine 
, deren Differenz x - y = 2 ist. Dazu habe ich eine Funktion
primzahlzwilling
geschrieben, die testet ob es zu einer Zahl x einen Primzahlzwilling
gibt.
Durch eine geschickte or-Verknüpfung in meiner Funktion werden sowohl Zwillinge grösser x als auch kleiner x gefunden.