Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 80

Der folgende applikative Algorithmus realisiert einen Primzahltest mithilfe einer Hilfsfunktion.

prim(x) =	if abs(x) ≤ 1then false else
	if x < 0	then prim(−x)
		else pr(2, x) fi fi
pr(x, y) =	if x ≥ y	then true
		else (y mod x) ≠ 0 ∧ pr (x + 1, y) fi

Die Hilfsfunktion pr(x, y) liefert genau dann den Wert true für wahr, wenn die Zahl y durch keine Zahl z, x ≤ z < y teilbar ist. Unter dieser Voraussetzung gilt sicher folgender Zusammenhang:

prim(x) (x > 1) ∧ pr (2, x)

Die applikative Lösung setzt diese Formel nun direkt um in einen Algorithmus. An zwei einfachen Beispielen kann man sich das Prinzip klar machen: Für prim (5) wird zunächst pr(2, 5) aufgerufen. Da 5 mod 2 = 1 ist, wird im nächsten Schritt pr(3, 5) aufgerufen, gefolgt von pr(4, 5) und schließlich pr(5, 5). Wegen 5 ≥ 5 ist die Abarbeitung beendet und pr(2, 5) liefert true. Betrachtet man dagegen prim(6), so liefert bereits der Aufruf von pr(2, 6) das Ergebnis false, da 6 mod 2 = 0.

Optimierung des Aufwandes des Primzahltests

Diese Lösung ist nicht sehr effizient, da unnötig viele Zahlen getestet werden. Bereits durch kleine Modifikationen kann man den Aufwand des Primzahltests deutlich verringern:

 Ersetze x ≥ y durch x · x > y. Der kleinster Teiler einer Nichtprimzahl ist sicher nie größer als deren Quadratwurzel!

 Ersetze pr(x + 1, y) durch if x = 2 then pr(3, y) else pr(x + 2, y) fi. Dies funktioniert, da 2 die einzige gerade Zahl sein kann, die kleinster Teiler einer Nichtprimzahl ist. Für das obige Beispiel wird nach pr(3, 5) also direkt pr(5, 5) ausgeführt.

Unendliche Berechnungen bei der Termauswertung führen zu undefinierten Werten. Das folgende Beispiel zeigt, dass mit undefinierten Werten vorsichtig umgegangen werden muss, um nicht widersprüchliche Aussagen zu bekommen.