Primzahlen: IIIa. Kapitel: Primzahlbestimmung
Einleitung
[Bearbeiten]Eine Primzahl ist eine natürliche Zahl größer Eins, die nur durch die Eins und sich selbst teilbar ist
[Bearbeiten]Die naheliegenste Methode zu testen, ob es sich bei einer natürlichen Zahl um eine Primzahl handelt, ist, zu prüfen, ob es eine natürliche Zahl mit gibt, die teilt. Zu prüfen, ob von geteilt wird, ist überflüssig, da und in jedem Fall teilerfremd sind.
Ein Programm dazu:
do forever say "Bitte gib eine natürliche Zahl ein (Programm beenden mit 0):" pull n if (n = 0) then leave t = 0 do i = 2 to n-2 if ((n // i) = 0) then t = 1 end if (t = 0) then say "Die Zahl "||n||" ist eine Primzahl" if (t = 1) then say "Die Zahl "||n||" ist keine Primzahl" end
Verbesserungsmöglichkeiten des konsequenten Durchtesten
[Bearbeiten]Man kann das Verfahren des konsequenten Durchtesten auf unterschiedliche Arten verbessern:
- Wenn aus einem beliebigen Produkt mit der Faktor schon als Teiler getestet wurde, so ist es nicht mehr nötig, Faktor auch noch zu testen.
- Angenommen ich teste die Zahl 35 = 5·7 auf ihre primalität. Wenn ich die 5 getestet und festgestellt habe, das sie ein Teiler von 35 ist, kann ich aufhören, weitere Zahlen darauf zu testen, ob sie Faktoren der 35 sind oder nicht. Um mal den Extremfall zu zeigen: Angenommen ich will 49 auf ihre primalität testen. Dann muß ich das nur bis zur 7 machen, weil 7 die Quadratwurzel von 49 ist: 7·7 = 49.
- Wie sieht das nun bei einer Primzahl aus? Wie weit muß ich da testen? Bis ? Nein, es reicht, bis zu testen. Warum?
- Angenommen, es gibt keinen Teiler kleiner , der teilt. Dann kann es auch keinen Teiler größer geben, der teilt. Warum?
- Nehmen wir mal an, wir haben zwei natürliche Zahlen für die gilt teilt und teilt . Daraus würde folgen, das ist. Das ist ein Widerspruch, und deshalb muß man auch nur bis maximal testen.
- Primzahlen größer 3 haben die Form oder
- Aus diesem Grund braucht man Primzahlen, die nicht dieser Form entsprechen nicht kosequent auf alle mögliche Teiler zu testen. Es reicht, einen Vortest auf die Formen und zu machen. Zahlen die nicht diesen Formen entsprechen, fallen als Kandidaten für Primzahlen gleich raus. Das sind aller natürlichen Zahlen.
Ein Programm, das alle Verbesserungen berücksichtigt, könnte so aussehen:
do forever say "Bitte gib eine natürliche Zahl ein (Programm beenden mit 0):" pull n if (n = 0) then leave t = 1 t2 = ((n-1)//6)*((n+1)//6) t3 = (n-2)*(n-3) if ((n > 3) && (t2 = 0)) then do t = 0 do i = 2 to sqrt(n) if ((n // i) = 0) then t = 1 end end if (t3 = 0) then t = 0 if (t = 0) then say "Die Zahl "||n||" ist eine Primzahl" if (t = 1) then say "Die Zahl "||n||" ist keine Primzahl" end
Serie
[Bearbeiten]Angenommen, man möchte einen ganzen Bereich von 1 bis zu einer bestimmten Oberzahl auf Primzahlen durchsuchen. Dann wäre es nicht sinnvoll, so man das konsequente Durchtesten verwenden würde, immer wieder mit Null anzufangen. Also so ein Programm:
say "Bitte gib eine Obergrenze ein:" pull n do i2 = 2 to n if (n = 0) then leave t = 1 t2 = ((n-1)//6)*((n+1)//6) t3 = (n-2)*(n-3) if ((n > 3) && (t2 = 0)) then do t = 0 do i = 2 to sqrt(n) if ((n // i) = 0) then t = 1 end end if (t3 = 0) then t = 0 if (t = 0) then say n end pull x
wäre nicht sinnvoll. Besser ist es, schon gefundene Primzahlen im Programm zu speichern:
Wenn man testen möchte, ob eine natürliche Zahl eine Primzahl ist, kommt einem vielleicht als erstes das Konsequente Durchtesten auf Teilbarkeit in den Sinn. Dabei testet man, ob es eine natürliche Zahl zwischen 2 und gibt, die teilt. Existiert keine natürliche Zahl zwischen 2 und gibt, die teilt, so ist eine Primzahl. Findet sich wenigstens eine Zahl zwischen 2 und die teilt, so ist keine Primzahl.
Das Sieb des Eratosthenes
[Bearbeiten]Das Sieb des Eratosthenes ist ein altes Verfahren, um alle Primzahlen zwischen 2 und einer fest vorgebenen Obergrenze aus den natürlichen Zahlen herauszufiltern. Dabei speichert man alle Zahlen zwischen 2 und Obergrenze in ein Array und markiert sie als Primzahlen. Dann beginnt das Sieben: Die kleinste Zahl, die als Primzahl markiert ist wird herausgesucht (das ist zu Anfang die 2), nun werden alle Vielfachen der Primzahl, beginnend mit dem Quadrat der Primzahl als Nichtprimzahlen markiert. Nach diesem Durchlauf, wird die nächstgrößere Zahl herausgesucht, die als Primzahl markiert ist. Das Ganze läuft solange ab, bis die nächste Zahl größer als ist. Alle Zahlen, die jetzt noch als Primzahlen markiert sind, sind auch Primzahlen.
![](http://upload.wikimedia.org/wikipedia/commons/6/63/Animation_Sieb_des_Eratosthenes.gif)
obergrenze=10000 /* Initialisierung des Primzahlfeldes: Alle Zahlen größer gleich 2 */ /* sind Primzahlen */ do i=2 to obergrenze primzahlfeld.i=1 end /* Der Siebprozess beginnt hier */ do i=2 to sqrt(obergrenze) if (primzahlfeld.i=1) then do i2=i*i to n by i primzahlfeld.i2=0 end end /* Hier werden die Primzahlen ausgegeben */ do i=2 to n if (primzahlfeld.i=1) then say i;", "; end