Todos os desafios
Médio 0 resolvidos 0% de aceitação

Fatoração em Números Primos

Decomponha um número em fatores primos, listados do menor para o maior e com repetição.

O que você vai aprender

  • Dividir por cada fator tantas vezes quantas ele aparece
  • Parar as divisões assim que d × d passar do que resta
  • Reconhecer que uma sobra maior que 1 é um fator primo

Problema

Ver original (inglês)

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

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

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

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.