Algorithmen und Datenstrukturen

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:
n = 24
  1. p = 2, n = 24 (p wurde am Anfang der Schleife von 1 auf 2 erhöht) n % 2 == 0 ⇒ divisors = [2], powers = [0] n //= 2 ⇒ n = 12, powers = [1] n //= 2 ⇒ n = 6, powers = [2] n //= 2 ⇒ n = 3, powers = [3]
  1. p = 3, n = 3 ⇒ Abbruch der while-Schleife, denn p * p = 9, was grĂ¶ĂŸer als 2 ist
  1. n > 1 ⇒ divisors = [2, 3], powers = [3, 1]
n = 75
  1. p = 2, n = 75
  1. p = 3, n = 75 n % 3 == 0 ⇒ divisors = [3], powers = [0] n //= 3 ⇒ n = 25, powers = [1]
  1. p = 4, n = 25
  1. p = 5, n = 25 n % 5 == 0 ⇒ divisors = [3, 5], powers = [1, 0] n //= 5 ⇒ n = 5, powers = [1, 1] n //= 5 ⇒ n = 1, powers = [1, 2]
  1. p * p > n ⇒ Abbruch der while-Schleife ⇒ divisors = [3, 5], powers = [1, 2]
n = 84
  1. p = 2, n = 84 n % 2 == 0 ⇒ divisors = [2], powers = [0] n //= 2 ⇒ n = 42, powers = [1] n //= 2 ⇒ n = 21, powers = [2]
  1. p = 3, n = 21 n % 3 == 0 ⇒ divisors = [2, 3], powers = [2, 0] n //= 3 ⇒ n = 7, powers = [2, 1]
  1. p * p > n ⇒ Abbruch der while-Schleife
  1. n > 1 ⇒ divisors = [2, 3, 7], powers = [2, 1, 1]
n = 31
  1. p = 2, n = 31
  1. p = 3, n = 31
  1. p = 4, n = 31
  1. p = 5, n = 31
  1. p = 6, n = 31
  1. p * p > n ⇒ Abbruch der while-Schleife
  1. n > 1 ⇒ divisors = [31], powers = [1]

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

Eingabe
Ausgabe
8
2
24
3
75
5
31
31
Bonus: Warum prĂŒfen wir nicht nur Primzahlen?
Unsere aktuelle Implementierung des Algorithmus geht alle Zahlen von 2 bis durch. WĂ€re es nicht sinnvoller, nur Primzahlen in diesem Bereich zu testen?
Auf den ersten Blick klingt das logisch (und in manchen Aufgaben könnte man so vorgehen). Allerdings ist das Bestimmen aller Primzahlen bis (im Worst Case) aufwĂ€ndiger als einmal einfach alle Zahlen bis durchzugehen und zu prĂŒfen, ob sie Teiler von n sind (genauer gesagt ist das Verfahren zum Ermitteln der Primzahlen bis ). In vielen FĂ€llen braucht die Suche nach allen Primzahlen also mehr Zeit als das direkte Ausprobieren sĂ€mtlicher möglicher Kandidaten.
FÀllt Ihnen dennoch eine Situation ein, in der es lohnender wÀre, zuerst alle Primzahlen zu generieren und dann nur diese zur Primfaktorisierung zu nutzen?
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue