Problema
Todo inteiro maior que 1 pode ser escrito como produto de primos de uma única maneira, a menos da ordem dos fatores (é o teorema fundamental da aritmética). Por exemplo, 360 = 2 × 2 × 2 × 3 × 3 × 5. Encontrar essa lista é o que se chama fatoração em números primos.
Implemente prime_factorization(n).
n pode chegar a 10^12, então a abordagem clássica é a das divisões sucessivas: divida por 2 enquanto der, depois por 3, e assim por diante. Basta testar divisores d enquanto d × d ≤ a parte de n que ainda resta; o que sobrar acima de 1 no final é primo. Assim o trabalho fica em torno de √n ≈ 10^6 passos, mesmo quando n é um primo grande ou o produto de dois primos grandes.
Entrada
n: o número a ser fatorado.
Saída
Retorne os fatores primos de n em ordem crescente, repetindo cada primo tantas vezes quantas ele divide n, de modo que o produto da lista seja n. Para n = 1, retorne uma lista vazia. Se n for primo, a lista tem um único elemento, n.
Restrições
1 ≤ n ≤ 10^12
Exemplos
Entrada:
n = 360
Saída esperada:
expected = [2, 2, 2, 3, 3, 5]
Entrada:
long long n = 360;
Saída esperada:
std::vector<long long> expected = {2, 2, 2, 3, 3, 5};
Entrada:
long n = 360;
Saída esperada:
long[] expected = new long[] {2, 2, 2, 3, 3, 5};
Explicação
360 = 2 × 180 = 2 × 2 × 90 = 2 × 2 × 2 × 45 = 2 × 2 × 2 × 3 × 15 = 2 × 2 × 2 × 3 × 3 × 5, então a resposta é [2, 2, 2, 3, 3, 5].
Entrada:
n = 97
Saída esperada:
expected = [97]
Entrada:
long long n = 97;
Saída esperada:
std::vector<long long> expected = {97};
Entrada:
long n = 97;
Saída esperada:
long[] expected = new long[] {97};
Explicação
Nenhum primo até √97 ≈ 9,8 (2, 3, 5, 7) divide 97, então ele é primo e a resposta é [97].
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Divida por 2 enquanto der, depois passe para 3, 5, 7, e assim por diante.
Dica 2
Diminua n a cada fator encontrado e compare d × d com o n já reduzido.
Dica 3
Se sobrar algo maior que 1 depois do laço, esse é o maior fator primo.
Complexidade esperada
tempo O(√n), espaço extra O(log n) para o resultado
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.