Tutte le sfide
Media 0 risolte 0% di accettazione

Scomposizione in fattori primi

Scomponi un numero nei suoi fattori primi, elencati dal più piccolo al più grande e ripetuti.

Cosa imparerai

  • Dividere per ogni fattore tante volte quante compare
  • Fermare le divisioni quando d × d supera ciò che resta
  • Riconoscere che un resto maggiore di 1 è un fattore primo

Problema

Ogni intero maggiore di 1 si può scrivere come prodotto di numeri primi in un solo modo, a meno dell'ordine dei fattori (è il teorema fondamentale dell'aritmetica). Per esempio 360 = 2 × 2 × 2 × 3 × 3 × 5. Trovare questo elenco si chiama scomposizione in fattori primi.

Implementa prime_factorization(n).

n può arrivare a 10^12, quindi il metodo classico è quello delle divisioni successive: dividi per 2 finché puoi, poi per 3, e così via. Basta provare i divisori d finché d × d ≤ la parte di n che rimane ancora da scomporre; quello che alla fine resta, se è maggiore di 1, è a sua volta primo. In questo modo il lavoro resta intorno a √n ≈ 10^6 passi anche quando n è un primo grande o il prodotto di due primi grandi.

Input

n: il numero da scomporre.

Output

Restituisci i fattori primi di n in ordine crescente, ripetendo ogni primo tante volte quante divide n, in modo che il prodotto della lista sia n. Per n = 1 restituisci una lista vuota. Se n è primo, la lista contiene il solo elemento n.

Vincoli

1 ≤ n ≤ 10^12

Esempi

Esempio 1
Input:
n = 360

Output atteso:
expected = [2, 2, 2, 3, 3, 5]
Input:
long long n = 360;

Output atteso:
std::vector<long long> expected = {2, 2, 2, 3, 3, 5};
Input:
long n = 360;

Output atteso:
long[] expected = new long[] {2, 2, 2, 3, 3, 5};

Spiegazione

360 = 2 × 180 = 2 × 2 × 90 = 2 × 2 × 2 × 45 = 2 × 2 × 2 × 3 × 15 = 2 × 2 × 2 × 3 × 3 × 5, quindi la risposta è [2, 2, 2, 3, 3, 5].

Esempio 2
Input:
n = 97

Output atteso:
expected = [97]
Input:
long long n = 97;

Output atteso:
std::vector<long long> expected = {97};
Input:
long n = 97;

Output atteso:
long[] expected = new long[] {97};

Spiegazione

Nessun primo fino a √97 ≈ 9.8 (2, 3, 5, 7) divide 97, quindi 97 è primo e la risposta è [97].

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

Dividi per 2 finché puoi, poi passa a 3, 5, 7 e così via.

Suggerimento 2

Riduci n ogni volta che trovi un fattore e confronta d × d con il nuovo valore di n.

Suggerimento 3

Se dopo il ciclo resta qualcosa maggiore di 1, quello è il fattore primo più grande.

Complessità attesa

tempo O(√n), spazio aggiuntivo O(log n) per il risultato

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.