Problema
Um número primo é um inteiro maior que 1 que não possui divisores positivos além de 1 e ele mesmo. Encontre o maior fator primo de n. Quando n for primo, retorne n.
Implemente largest_prime_factor(n).
Entrada
n: O inteiro a ser fatorado.
Saída
Retorne seu maior divisor primo.
Restrições
2 ≤ n ≤ 10¹². A entrada 1 está excluída porque não possui fator primo.
Exemplos
Entrada:
n = 84
Saída esperada:
expected = 7Entrada:
long long n = 84;
Saída esperada:
long long expected = 7;Entrada:
long n = 84;
Saída esperada:
long expected = 7;Explicação
84 = 2 × 2 × 3 × 7, então o maior fator primo é 7.
Entrada:
n = 13
Saída esperada:
expected = 13Entrada:
long long n = 13;
Saída esperada:
long long expected = 13;Entrada:
long n = 13;
Saída esperada:
long expected = 13;Explicação
13 é primo, então ele mesmo é seu maior fator primo.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Remova primeiro os fatores primos pequenos; qualquer valor restante só pode diminuir, e o último fator sobrando é a resposta.
Dica 2
Teste divisores só até a raiz quadrada do restante atual e divida repetidamente quando couber.
Dica 3
Se o restante ainda for maior que 1 depois de testar os menores fatores, esse restante é primo e é o maior fator.
Complexidade esperada
tempo O(√n), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.