Ein einfaches Faktorisierungsverfahren

Probedivision

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 dividiert 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 = 3                      {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(n):
    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

Implementierung des Verfahrens

Das Verfahren kann wie folgt als Funktion in Python implementiert werden:

def primfaktoren(n):

    """ zerlegt eine Zahl in ihre Primfaktoren

    >>> primfaktoren(24)
    [2, 2, 2, 3]

    """

    faktoren = []
    z = n
    while z > 1:
        # bestimme den kleinsten Primfaktor p von z
        i = 2
        gefunden = False
        while i*i <= z and not gefunden:
            if z % i == 0:
                gefunden = True
                p = i
            else:
                i = i + 1
        if not gefunden:
            p = z
        # füge p in die Liste der Faktoren ein
        faktoren = faktoren + [p]
        z = z // p
    return faktoren

Aufgabe 1

Teste die Funktion primfaktoren(n). Wie zeigt sich, dass die Ausgangszahl eine Primzahl ist?

Aufgabe 2

Bestimme mit der Funktion primfaktoren(n) die Primfaktorzerlegung der beiden Zahlen 484639526894037745950720 und 565765434324543216797351. Was stellst du fest? Stelle eine Vermutung auf, warum es hier zu einem unterschiedlichen Laufzeitverhalten kommt.