Das Ganze wird durch das folgende Modul geleistet:
IMPLEMENTATION MODULE Zahlen;
(* Modul zur Faktorisierung natuerlicher Zahlen *)
(* Vorlesung EI1 WS 1999/2000 *)
(* Klaus Lagally, 09.11.1999 *)
FROM InOut IMPORT WriteCard, WriteString, WriteLn;
PROCEDURE Zerlege(n: CARDINAL);
(* bestimme die Primfaktorzerlegung der Zahl n *)
(* und gib sie in der Form n = f1*f2*...*fk aus *)
(* suche und drucke aufsteigend alle Teiler von n *)
VAR Teiler: CARDINAL;
BEGIN WriteCard(n,1); WriteString(* = *);
Teiler := 2;
WHILE Teiler < n
DO WHILE (n MOD Teiler) = 0
DO WriteCard(Teiler,1); WriteString(" * ");
n := n DIV Teiler
END;
Teiler := Teiler + 1
END;
WriteCard(n,1); WriteLn
END Zerlege;
END Zahlen.
Wir haben hier das Verfahren ausprogrammiert,
das wir bei der Arbeit mit Papier und Bleistift (oder Taschenrechner)
ohne Computer wohl auch verwendet hätten;
solch ein direkter Angriff, also die Übertragung
von alltäglichen Verfahren auf den Computer,
führt oft schnell zu guten Ansätzen.
Um sich von der korrekten Funktion zu überzeugen,
überlegt man sich am besten, was das Verfahren tut,
wenn n die Werte 0, 1, 2 hat oder
eine Primzahlpotenz oder eine allgemeine zerlegbare Zahl ist;
trotz der beiden geschachtelten Schleifen ist das
beim Schreibtischtest noch zu überblicken
(von der Verwendung eines "Debuggers" halten wir nicht viel).
Überraschenderweise gibt es auch eine äußerst einfache rekursive Lösung.