Mittel 0 gelöst 0% Erfolgsquote

Primfaktorzerlegung

Zerlege eine Zahl in ihre Primfaktoren, aufsteigend sortiert und mit Wiederholungen.

Das lernst du

  • Jeden Faktor so oft herausteilen, wie er vorkommt
  • Die Probedivision beenden, sobald d × d den Rest übersteigt
  • Erkennen, dass ein Rest größer als 1 ein Primfaktor ist

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

Beispiel 1
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].

Beispiel 2
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.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.