Problème
Un nombre premier est un entier strictement supérieur à 1 qui n'a pas d'autres diviseurs positifs que 1 et lui-même. Trouvez le plus grand facteur premier de n. Si n est lui-même premier, retournez n.
Implémentez largest_prime_factor(n).
Entrée
n : L'entier à factoriser.
Sortie
Retournez son plus grand diviseur premier.
Contraintes
2 ≤ n ≤ 10¹². L'entrée 1 est exclue car elle n'a pas de facteur premier.
Exemples
Entrée :
n = 84
Sortie attendue :
expected = 7Entrée :
long long n = 84;
Sortie attendue :
long long expected = 7;Entrée :
long n = 84;
Sortie attendue :
long expected = 7;Explication
84 = 2 × 2 × 3 × 7, donc le plus grand facteur premier est 7.
Entrée :
n = 13
Sortie attendue :
expected = 13Entrée :
long long n = 13;
Sortie attendue :
long long expected = 13;Entrée :
long n = 13;
Sortie attendue :
long expected = 13;Explication
13 est premier, donc il est son propre plus grand facteur premier.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Supprime d’abord les petits facteurs premiers ; la valeur restante ne peut que diminuer, et le dernier facteur est la réponse.
Indice 2
Teste les diviseurs seulement jusqu’à la racine carrée du reste courant, puis divise-le plusieurs fois s’il passe.
Indice 3
Si le reste est encore > 1 après les petits facteurs, alors ce reste est premier et c’est le plus grand facteur.
Complexité attendue
temps O(√n), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.