Primfaktorzerlegung

Primzahlen als Bausteine der natürliche Zahlen

Jede natürliche Zahl größer als 1 lässt sich als Produkt von Primzahlen schreiben. Diese Darstellung ist bis auf die Reihenfolge der Faktoren eindeutig.

Beispiel: Die Zahl 260 kann wie folgt mit Primzahlen aufgebaut werden:

260 = 2*2*5*13 = 22*5*13

Man nennt die Primzahlen, die in einer Produktdarstellung einer gegebenen Zahl vorkommen, auch Primfaktoren der Zahl.

Das Faktorisierungsproblem besteht darin, eine vorgegebene Zahl in ein Produkt aus Primfaktoren zu zerlegen.

Aufgabe 1

(a) Bei kleineren Zahlen kann man eine Primfaktorzerlegung oft direkt angeben. Bestimme eine Primfaktorzerlegung von n = 48 und n = 100.

(b) Bei größeren Zahlen sollte man systematisch vorgehen, um die Primfaktoren zu bestimmen. Bestimme eine Primfaktorzerlegung von n = 221 und n = 585. Wie könnte man hier vorgehen?

Ein einfaches Faktorisierungsverfahren

Ein einfaches Faktorisierungsverfahren basiert auf dem Verfahren der Probedivision: Wenn n die vorgegebene natürlich Zahl bezeichnet, dann dividiert man probeweise n der Reihe nach durch alle Zahlen von 2 aufwärts, bis die Division aufgeht oder die Wurzel aus n als Grenze erreicht wird. Wenn auf diese Weise ein Primfaktor gefunden wird, so wird er in einer Liste zur Verwaltung sämtlicher Primfaktoren aufgenommen. Die Ausgangszahl wird durch den Primfaktor divividiert und das Verfahren wird mit dem Quotienten analog durchgeführt. Das Verfahren endet, wenn die zu überprüfende Zahl eine Primzahl ist. Diese wird dann ebenfalls in der Liste der Primfaktoren aufgenommen.

Die folgende Übersicht verdeutlicht das Verfahren am Beispiel n = 51.

# Übergabe
n = 51
# Initialisierung
faktoren = []              {faktoren -> []}
z = n                      {z -> 51}
# Probedivisionen
z % 2 -> 1
z % 3 -> 0
# Aktualisierung
p = z                      {p -> 3}
faktoren = faktoren + [p]  {faktoren -> [3]}
z = z // p                 {z -> 17}
# Probedivisionen
z % 2 -> 1
z % 3 -> 2
z % 4 -> 1
z % 5 -> 2
# Aktualisierung
p = z                      {p -> 17}
faktoren = faktoren + [p]  {faktoren -> [3, 17]}
z = z // p                 {z -> 1}
# Rückgabe
[3, 17]

Allgemein beschreiben lässt sich das Verfahren mit dem folgenden Algorithmus:

ALGORITHMUS primfaktoren:
    Übergabe: n // natürliche Zahl größer 1
    initialisiere die Liste faktoren: faktoren = []
    initialisiere die Hilfsvariable z: z = n
    SOLANGE z > 1:
        bestimme den kleinsten Primfaktor p von z mit Probedivisionen
        füge p in die Liste faktoren ein
        z = z // p
    Rückgabe: faktoren

Das Verfahren soll als Funktion in Python implementiert werden:

Aufgabe 2

Entwickle eine Funktionsdefinition für diese Funktion (mit integrierten Testfällen). Teste den Funktionsbaustein gründlich.