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