Primzahlen: IIIa. Kapitel: Primzahlbestimmung

Primzahlen

Probedivision durch alle möglichen Teiler

Auf Grund der Definition "Eine Primzahl ist eine natürliche Zahl größer Eins, die nur durch die Eins und sich selbst teilbar ist" ist die naheliegenste Methode zu testen, ob es sich bei einer natürlichen Zahl $n$ um eine Primzahl handelt, 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 in Pseudocode dazu:

do forever
    output "Bitte gib eine natürliche Zahl ein (Programm beenden mit 0): "
    n := input()
    if n == 0 Abbruch
    possible_prime := True
    t := 2
    while possible_prime and (t <= sqrt(n))
        if (n mod t == 0)
            possible_prime := False 
        t := t + 1
    if possible_prime 
        output (n, "ist eine Primzahl")
    else 
        output (n, "ist keine Primzahl")

Verbesserungsmöglichkeiten des konsequenten Durchtestens

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 oder gleich $\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 muss man auch nur bis maximal $\left\lfloor {\sqrt {n}}\right\rfloor$ testen.

• Primzahlen größer 3 haben die Form $6k+1$ oder $6k-1$, weil sie ungerade und nicht durch 3 teilbar sind.

Aus diesem Grund braucht man Primzahlen, die nicht dieser Form entsprechen nicht konsequent auf alle möglichen Teiler zu testen. Es reicht, einen Vortest auf die Formen $6k+1$ und $6k-1=6(k-1)+5$ 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
    output "Bitte gib eine natürliche Zahl ein (Programm beenden mit 0): "
    n := input()
    if n == 0 Abbruch
    possible_prime := True
    m = n mod 6
    if (n > 3) and (m == 1 or m == 5)
        t := 5
        while possible_prime and (t <= sqrt(n))
            if (n mod t == 0) or (n mod (t+2) == 0)
                possible_prime := False 
            t := t + 6
    else                                                   // n <= 3
        if 1 < n < 4
            possible_prime := True
        else:
            possible_prime := False
    if possible_prime 
        output (n, "ist eine Primzahl")
    else 
        output (n, "ist keine Primzahl")

Serie

Angenommen, man möchte einen ganzen Bereich von 1 bis zu einer bestimmten Obergrenze 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:

do forever
    output "Bitte gib eine Obergrenze ein (Programm beenden mit 0): "
    limit := input()
    if limit == 0 Abbruch
    for n = 2 to limit
        possible_prime := True
        m := n mod 6
        if (n > 3) and (m == 1 or m == 5)
            t := 5
            while possible_prime and (t <= sqrt(n))
                if (n mod t == 0) or (n mod (t+2) == 0)
                    possible_prime := False 
                t := t + 6
        else                                                   // n <= 3
            if 1 < n < 4
                possible_prime := True
            else:
                possible_prime := False
        if possible_prime 
            output (n)

wäre nicht sinnvoll. Besser ist es, schon gefundene Primzahlen im Programm zu speichern.

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