Problem
Jede ganze Zahl größer als 1 lässt sich bis auf die Reihenfolge der Faktoren auf genau eine Weise als Produkt von Primzahlen schreiben (der Fundamentalsatz der Arithmetik). Zum Beispiel ist 360 = 2 × 2 × 2 × 3 × 3 × 5. Diese Liste zu bestimmen nennt man Primfaktorzerlegung.
Implementiere prime_factorization(n).
n kann bis zu 10^12 groß sein, deshalb ist die klassische Methode die Probedivision: Teile so oft wie möglich durch 2, dann durch 3 und so weiter. Du musst Teiler d nur ausprobieren, solange d × d höchstens so groß ist wie der noch verbleibende Teil von n; was am Ende größer als 1 übrig bleibt, ist selbst eine Primzahl. So bleibt der Aufwand bei etwa √n ≈ 10^6 Schritten, selbst wenn n eine große Primzahl oder das Produkt zweier großer Primzahlen ist.
Eingabe
n: Die zu zerlegende Zahl.
Ausgabe
Gib die Primfaktoren von n in aufsteigender Reihenfolge zurück, wobei jede Primzahl so oft vorkommt, wie sie n teilt, sodass das Produkt der Liste n ergibt. Für n = 1 gibst du eine leere Liste zurück. Ist n eine Primzahl, enthält die Liste nur das eine Element n.
Einschränkungen
1 ≤ n ≤ 10^12
Beispiele
Eingabe:
n = 360
Erwartete Ausgabe:
expected = [2, 2, 2, 3, 3, 5]
Eingabe:
long long n = 360;
Erwartete Ausgabe:
std::vector<long long> expected = {2, 2, 2, 3, 3, 5};
Eingabe:
long n = 360;
Erwartete Ausgabe:
long[] expected = new long[] {2, 2, 2, 3, 3, 5};
Erläuterung
360 = 2 × 180 = 2 × 2 × 90 = 2 × 2 × 2 × 45 = 2 × 2 × 2 × 3 × 15 = 2 × 2 × 2 × 3 × 3 × 5, also lautet die Antwort [2, 2, 2, 3, 3, 5].
Eingabe:
n = 97
Erwartete Ausgabe:
expected = [97]
Eingabe:
long long n = 97;
Erwartete Ausgabe:
std::vector<long long> expected = {97};
Eingabe:
long n = 97;
Erwartete Ausgabe:
long[] expected = new long[] {97};
Erläuterung
Keine Primzahl bis √97 ≈ 9,8 (2, 3, 5, 7) teilt 97, also ist 97 prim und die Antwort lautet [97].
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Teile durch 2, solange es geht, dann weiter mit 3, 5, 7 und so weiter.
Hinweis 2
Verkleinere n bei jedem gefundenen Faktor und vergleiche d × d mit dem verkleinerten n.
Hinweis 3
Bleibt nach der Schleife etwas größer als 1 übrig, ist das der größte Primfaktor.
Erwartete Komplexität
Zeit O(√n), zusätzlicher Speicher O(log n) für das Ergebnis
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.