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.

 
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