Lisp lernen, Teil 1: Primzahlen berechnen

Die Syntax von Lisp ist minimalistisch, dennoch (oder gerade deswegen) birgt die Sprache ein enormes Potenzial. Um Lisp zu lernen und zu üben, hilft das regelmäßige Schreiben von Code mehr als eine rein theoretische Beschäftigung mit der Sprache. Zum Auftakt ist das Ziel eine Funktion zum Berechnen von Primzahlen.

In Pocket speichern vorlesen Druckansicht 18 Kommentare lesen
Lesezeit: 6 Min.
Von
  • Golo Roden
Inhaltsverzeichnis

Die Syntax von Lisp ist minimalistisch, dennoch (oder gerade deswegen) birgt die Sprache ein enormes Potenzial. Um Lisp zu lernen und zu üben, hilft das regelmäßige Schreiben von Code mehr als eine rein theoretische Beschäftigung mit der Sprache. Zum Auftakt ist das Ziel eine Funktion zum Berechnen von Primzahlen.

Gesucht ist eine Funktion get-primes, die die Parameter min und max entgegennimmt und eine Liste aller Primzahlen zurückgibt, die sich im durch min und max definierten Intervall befinden. Enthält das Intervall keine Primzahlen, ist die leere Liste zurückzugeben. Ist max kleiner als min, ist die Rückgabe ebenfalls die leere Liste.

Das Grundgerüst für die Funktion get-primes lässt sich leicht definieren, wobei zunächst eine statische Liste mit den Primzahlen zwischen 1 und 20 zurückgegeben wird, unabhängig von den Parametern min und max:

(defun get-primes (min max)
'(2 3 5 7 11 13 17 19))

Im nächsten Schritt ist es sinnvoll, über alle Zahlen zwischen min und max zu iterieren und sie dynamisch als Liste aufzubauen. Sie lässt sich dann nämlich in einem weiteren Schritt filtern. Dazu dient das loop-Makro in Verbindung mit collect. Da es sich bei den Zahlen zwischen min und max nicht zwingend um Primzahlen handelt, kann man die Laufvariable beispielsweise guess nennen, um den Umstand auszudrücken, dass es sich vorerst nur um eine Vermutung handelt:

(defun get-primes (min max)
(loop
for guess from min to max
collect guess))

Als Nächstes ist das Sammeln der Zahlen auf jene einzuschränken, die tatsächlich Primzahlen sind. Angenommen, es gäbe eine Prädikatsfunktion is-prime, ließe sich das wie folgt schreiben:

(defun get-primes (min max)
(loop
for guess from min to max
when (is-prime guess)
collect guess))

Da die Funktion is-prime nicht existiert, gilt es nun, sie zu definieren. Dazu ist ein Blick auf den Wikipedia-Eintrag von Primzahlen hilfreich. Dort heißt es:

"Eine Primzahl ist eine natürliche Zahl, die genau zwei natürliche Zahlen als Teiler hat. Eine Primzahl ist also eine natürliche Zahl größer als 1, die nur durch sich selbst und durch 1 ganzzahlig teilbar ist."

Da jede natürliche Zahl durch sich selbst und durch 1 teilbar ist, werden die beiden Teiler als "triviale Teiler" bezeichnet. Das Gegenteil davon sind die "nichttrivialen Teiler", die zwischen 1 und der zu teilenden Zahl liegen müssen.

Im ersten Schritt lässt sich die Funktion is-prime daher so definieren, dass sie nur Zahlen akzeptiert, die größer als 1 sind:

(defun is-prime (guess)
(> guess 1))

Zusätzlich gilt es zu überprüfen, ob die Zahl nur triviale Teiler besitzt – oder, mit anderen Worten, ob sie keine nichttrivialen Teiler besitzt:

(defun is-prime (guess)
(and (> guess 1)
(not (has-non-trivial-divisors guess))))

Für die Funktion has-non-trivial-divisors lässt sich mit Hilfe der rem-Funktion schreiben. Sie ermittelt den Rest einer Modulo-Division. Um beispielsweise zu prüfen, ob eine Zahl durch 2 teilbar ist, lässt sich has-non-trivial-divisors wie folgt definieren:

(defun has-non-trivial-divisors (n)
(zerop (rem n 2)))

Die Prädikatsfunktion zerop prüft dabei, ob der ihr übergebene Wert gleich 0 ist. Auf dem Weg liefert die Funktion den Wahrheitswert T für alle Zahlen, die durch 2 teilbar sind. Für alle anderen gibt die Funktion NIL zurück.

Nun gilt es aber, nicht nur die 2, sondern alle möglichen Teiler zu überprüfen. Das lässt sich erneut mit dem loop-Makro lösen. Allerdings lässt sich die Schleife abbrechen, sobald ein erster Teiler gefunden wurde. Wie viele Teiler es tatsächlich gibt, ist für die Frage, ob es überhaupt Teiler gibt, unerheblich:

(defun has-non-trivial-divisors (n)
(loop
for i from 2 to (1- n)
thereis (zerop (rem n i))))

Zum Verbessern der Leistung bietet es sich an, die Schleife nicht bis n-1 auszuführen, sondern nur bis zur Quadratwurzel von n. Wurde dann noch kein Teiler gefunden, kann es auch keinen mehr geben:

(defun has-non-trivial-divisors (n)
(loop
for i from 2 to (sqrt n)
thereis (zerop (rem n i))))

Nun sind die Funktion get-primes und alle Abhängigkeiten implementiert. Ruft man die Funktion mit den Werten 1 und 20 auf, gibt sie die ersten acht Primzahlen korrekt aus:

(get-primes 1 20)
; => (2 3 5 7 11 13 17 19)

Der Aufruf der Funktion mit einem Intervall, in dem sich keine Primzahlen befinden, liefert wie gefordert die leere Liste zurück:

(get-primes 8 10)
; => NIL

Ruft man die Funktion schließlich mit vertauschten min- und max-Werten auf, ist das Ergebnis ebenfalls die leere Liste:

(get-primes 20 1)
; => NIL

Die Aufgabe ist somit gelöst. Ein Blick auf den Code zeigt, wie elegant und zugleich mächtig das loop-Makro ist. Eine hervorragende Einführung in das Thema findet sich im 22. Kapitel des Buchs "Practical Common Lisp" von Peter Seibel.

tl;dr: Das Berechnen von Primzahlen lässt sich in Lisp gut mit dem loop-Makro lösen, das vielfältige Möglichkeiten bietet, zu iterieren. Auch wenn die Rechenleistung des gezeigten Ansatzes deutlich verbesserungswürdig ist, zeigt das Beispiel doch gut, wie das Makro genutzt werden kann. ()