Primfaktorisierung

Jede positive ganze Zahl n ≥ 2 lässt sich als Produkt von Primzahlen darstellen:

Das Ermitteln der Primfaktoren einer Zahl hat zahlreiche Anwendungen. So kann man damit leicht die Anzahl ihrer Teiler bestimmen, ein Gefühl für den größten gemeinsamen Teiler (GCD) und das kleinste gemeinsame Vielfache (LCM) zweier Zahlen bekommen und vieles mehr.

Um eine Zahl n (zum Beispiel 300) in ihre Primfaktoren zu zerlegen, beginnt man mit der kleinsten Primzahl p (2). Ist n durch p teilbar, teilt man so lange durch p, bis das nicht mehr möglich ist (300 / 2 = 150, 150 / 2 = 75).

Nach Abschluss dieser Teilungen erhöht man p um 1 (p = 3) und testet, ob das neue p ein Teiler von n ist. Falls ja, führt man auch hier so lange Divisionen durch, bis n nicht weiter teilbar ist (75 / 3 = 25).

Dann wird p wieder um 1 erhöht (p = 4). Da p selbst nicht mehr prim sein muss, kann es vorkommen, dass n trotzdem nicht durch 4, 6, 8 usw. teilbar ist, wenn alle passenden Primfaktoren bereits ausgeschöpft wurden. Im Beispiel wurde 300 mehrmals durch 2 geteilt, sodass nachher keine Teiler mehr übrig bleiben, die Vielfache von 2 sind. Da man schrittweise vom kleinsten zum größten möglichen Teiler vorgeht, bleiben nur noch echte Primzahlen übrig, die den Rest von n teilen können.

Beim nächsten Schritt erhöht man den Divisor erneut um 1 (p = 5) und wiederholt das Prozedere (75 / 5 = 5, 5 / 5 = 1). Dieser Vorgang läuft, bis der aktuelle Divisor größer ist als . An diesem Punkt ist das, was von n noch übrig bleibt, selbst eine Primzahl, und man kann diesen Wert als letzten Primfaktor zum Ergebnis hinzufügen.

Auf diese Weise erhalten wir für das Beispiel 300 die Zerlegung .

n = ...                              # Stelle n als Produkt von Primzahlen dar
p, divisors, powers = 1, [], []      # Primfaktor, Teiler und deren Exponenten

while p * p <= n:                    # solange p <= sqrt(n)
    p += 1                           # Erhöhe den möglichen Primfaktor p
    if n % p != 0:                   # Falls n nicht durch p teilbar ist, überspringen
        continue
    
    divisors.append(p)               # n % p == 0 => p ist ein Primfaktor
    powers.append(0)                 # Exponentinitialisierung auf 0
    while n % p == 0:                # so oft wie möglich teilen
        n //= p
        powers[-1] += 1              # pro Division den Exponenten um 1 erhöhen

if n > 1:                            # wenn p > sqrt(n) => n ist selbst ein Primfaktor
    divisors.append(n)
    powers.append(1)

print(list(zip(divisors, powers)))   # Ausgabe der Faktoren zusammen mit ihren Exponenten

In jeder Iteration des Algorithmus wird die Zahl, falls möglich, durch ihren aktuellen Primfaktor geteilt. Der Exponent dieses Faktors wird dabei pro erfolgreicher Division um 1 erhöht.

Schauen wir uns den Ablauf des Algorithmus an ein paar Beispielen an:

Aufgabe

Gegeben ist eine ganze Zahl n. Bestimmen Sie den größten Primfaktor von n.

Eingabe

Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl n (2 ≤ n ≤ ).

Ausgabe

Das Programm soll den größten Primfaktor von n ausgeben.

Beispiele