Mittel 0 gelöst 0% Erfolgsquote

Prime Factorization

Break a number into its prime factors, listed from smallest to largest with repetition.

Das lernst du

  • Divide out each factor as many times as it occurs
  • Stop trial division once d × d exceeds what is left
  • Recognise that a leftover above 1 is a prime factor

Problem

Übersetzung anzeigen

Every integer greater than 1 can be written as a product of primes in exactly one way, apart from the order of the factors (the fundamental theorem of arithmetic). For example, 360 = 2 × 2 × 2 × 3 × 3 × 5. Finding that list is called prime factorization.

Implement prime_factorization(n).

n can be as large as 10^12, so the classic approach is trial division: divide out 2 as long as you can, then 3, and so on. You only need to try divisors d while d × d ≤ the part of n that is still left; whatever remains above 1 at the end is itself prime. That keeps the work to about √n ≈ 10^6 steps even when n is a large prime or the product of two large primes.

Input

n: The number to factor.

Output

Return the prime factors of n in ascending order, repeating each prime as many times as it divides n, so that the product of the list is n. For n = 1 return an empty list. If n is prime, the list has the single 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, so the answer is [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

No prime up to √97 ≈ 9.8 (2, 3, 5, 7) divides 97, so it is prime and the answer is [97].

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Divide by 2 while you can, then move to 3, 5, 7, and so on.

Hinweis 2

Shrink n each time you find a factor, and compare d × d with the shrunken n.

Hinweis 3

If something greater than 1 is left after the loop, it is the largest prime factor.

Erwartete Komplexität

O(√n) time, O(log n) extra space for the result

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.