Primzahlen: IIIa. Kapitel: Primzahlbestimmung

Primzahlen

Eine Primzahl ist eine natürliche Zahl größer Eins, die nur durch die Eins und sich selbst teilbar ist

Die naheliegenste Methode zu testen, ob es sich bei einer natürlichen Zahl $n$ um eine Primzahl handelt, ist, zu prüfen, ob es eine natürliche Zahl $t$ mit $2\leq t\leq n-2$ gibt, die $n$ teilt. Zu prüfen, ob $n$ von $n-1$ geteilt wird, ist überflüssig, da $n$ und $n-1$ 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

Man kann das Verfahren des konsequenten Durchtesten auf unterschiedliche Arten verbessern:

• Wenn aus einem beliebigen Produkt $a\cdot b=n$ mit $a<b$ der Faktor $a$ schon als Teiler getestet wurde, so ist es nicht mehr nötig, Faktor $b\$ 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 $n-2$? Nein, es reicht, bis $\left\lfloor {\sqrt {n}}\right\rfloor$ zu testen. Warum?

Angenommen, es gibt keinen Teiler kleiner $\left\lfloor {\sqrt {n}}\right\rfloor$, der $n$ teilt. Dann kann es auch keinen Teiler größer $\left\lfloor {\sqrt {n}}\right\rfloor$ geben, der $n$ teilt. Warum?

Nehmen wir mal an, wir haben zwei natürliche Zahlen $\left\lfloor {\sqrt {n}}\right\rfloor <a\leq b$ für die gilt $a$ teilt $n$ und $b$ teilt $n$. Daraus würde folgen, das $(\left\lfloor {\sqrt {n}}\right\rfloor )^{2}=n<a\cdot b$ ist. Das ist ein Widerspruch, und deshalb muß man auch nur bis maximal $\left\lfloor {\sqrt {n}}\right\rfloor$ testen.

• Primzahlen größer 3 haben die Form $6k+1$ oder $6k-1$

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 $6k+1$ und $6k-1$ zu machen. Zahlen die nicht diesen Formen entsprechen, fallen als Kandidaten für Primzahlen gleich raus. Das sind ${\tfrac {2}{3}}$ 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

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 $n$ 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 $n-1$ gibt, die $n$ teilt. Existiert keine natürliche Zahl zwischen 2 und $n-1$ gibt, die $n$ teilt, so ist $n$ eine Primzahl. Findet sich wenigstens eine Zahl zwischen 2 und $n-1$ die $n$ teilt, so ist $n$ keine Primzahl.

Das Sieb des Eratosthenes

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 ${\sqrt {\text{Obergrenze}}}$ 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