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

Maior Fator Primo

Encontre o maior número primo que divide um inteiro positivo.

O que você vai aprender

  • Dividir os fatores do menor para o maior
  • Parar na raiz quadrada do que sobrou
  • Tratar números grandes com eficiência

Problema

Ver original (inglês)

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

Exemplo 1
Entrada:
n = 84

Saída esperada:
expected = 7
Entrada:
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.

Exemplo 2
Entrada:
n = 13

Saída esperada:
expected = 13
Entrada:
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.

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

# Programador Linguagem Tempo Memória Avaliação da IA Solução
1 ННикита Python 949 ms - 4/5 Ver código
2 KKKaneki Ken Python 1,000 ms - 3/5 Ver código

Aprenda com outros

Soluções da comunidade

Atenção: 2 soluções completas abaixo Tente resolver sozinho primeiro. Você ainda pode espiar o código de outros desenvolvedores e as avaliações da IA. Entre e resolva o desafio para participar da discussão.