Primzahlen

Bekanntlich sind Primzahlen natürliche Zahlen, die sich ohne Rest nur durch 1 und sich selbst teilen lassen. Will man eine Zahl testen, ob sie Primzahl ist, wird man versuchen, sie ohne Rest durch andere Zahlen zu teilen. Gelingt dies nicht, hat man eine Primzahl gefunden.

Die Idee

wir geben zunächst eine Zahl vor und testen, ob sie ohne Rest durch eine kleinere Zahl teilbar ist, die allerdings größer als 1 sein muss. Wenn ja, dann haben wir keine Primzahl. Das entsprechende Prädikat in Prolog soll daher unprim heißen. unprim ist wahr, wenn die vorgegebene Zahl keine Primzahl ist.
Das Prädikat prim testet nur, ob unprim falsch ist. Wir haben dann eine Primzahl vorliegen, die anzuzeigen ist.
Schließlich hilft ein rekursiv definiertes Prädikat allprim, alle natürlichen Zahlen in einem vorgegebenen Bereich zu testen.

Die Werkzeuge

Um Divisionsreste zu berechnen, nutzen wir die Funktion A mod B, die eine ganze Zahl A durch B teilt und als Ergebnis den Rest liefert.
Um den Wahrheitswert eines Prädikats umzukehren, gibt es das Prädikat not(), also für das Prädikat pred() not(pred(..)) .
Es kann sinnvoll sein, dass eine Klausel immer falsch sein soll, damit weitere Klauseln des Prädikats getestet werden. Dies erreicht man, indem man nach :- als letztes Prädikat fail einfügt.
Wir benötigen an verschiedenen Stellen Vergleiche:

A=B
A==B
A\==B
A=:=B
A=\=B
A<B
A=<B
A>B
A>=B
A wird gleichgesetzt mit B
A gleich B in allen Eigenschaften
A ungleich B
Zahlenwerte von A und B gleich
Zahlenwerte von A und B verschieden
A kleiner als B
A kleiner oder gleich B
A größer B
A größer oder gleich B

Vergleiche sind wie andere Prädikate zu verwenden.

Das Programm

unprim(X,T):- T > 1, 0 is X mod T.
unprim(X,T):- T > 1, Z is T-1, unprim(X,Z).

prim(X):- X > 1, Y is X - 1, not(unprim(X,Y)), write(X), write(',').

allprim(X):- prim(X), fail.
allprim(X):- X > 1, Z is X-1,allprim(Z).

Test, ob X durch T ohne Rest teilbar ist; wenn ja oder T=1, Schleifenende
Rekursive Schleife, bei der T um 1 verringert wird, dann Aufruf der 1.Klausel unprim
Test, ob unprim(X,X-1) falsch ist (not!); wenn ja Ausgabe von X als Primzahl

Test, ob X Primzahl ist, Klausel immer falsch, daher Anwenden der 2.Klausel allprim
Rekursive Schleife, Ende bei X=1, dabei immer Aufruf der 1.Klausel allprim

Was geschieht im Einzelnen?
Werden in einer Klausel rechts von :- mehrere Prädikate aufgerufen, so testet der Rechner von links nach rechts, ob diese Prädikate mit den vorgegebenen Parametern wahr sind. Ist ein Prädikat falsch, so bricht der Test ab, und die Klausel wird als falsch bewertet. Nur wenn alle Prädikate wahr sind, ist auch die Klausel wahr. Wird ein Prädikat getestet, so testet der Rechner von oben nach unten die zugehörigen Klauseln, bis er eine wahre findet. Der Test wird dann abgebrochen, und das Prädikat gilt als wahr. Sind alle zugehörigen Klauseln falsch, so ist es auch das Prädikat.

Für allprim bedeutet das, dass zunächst die erste Klausel allprim(X):-prim(X),fail getestet wird. Ist prim falsch, bricht der Test ab. Ist hingegen prim(X) wahr, so geht der Rechner zu fail, was dann immer falsch ist. Die erste Klausel ist damit immer falsch, und es wird die zweite Klausel allprim(X) getestet. Diese Klausel ist immer richtig, bis X den Wert 1 hat. Man erhält so eine Schleife.

Für das Prädikat unprim ist es komplizierter: Ist die erste Klausel unprim(X,T):-T>1,0 is X mod T. richtig, also 0 der Divisionsrest X mod T, so wird die zweite Klausel nicht mehr durchlaufen, und unprim ist wahr. Ist die erste Klausel falsch, so wird die zweite Klausel getestet, die mit einem neuen T ein weiteres Mal unprim aufruft. Es entsteht eine Schleife, bis ein Teiler von X gefunden wurde.

Aufgabe: Man schreibe ein Programm, das zu einer vorgegebenen Zahl N alle Teiler findet (Divisionsreste also 0).