Problema
Un número primo es un entero mayor que 1 que no tiene divisores positivos distintos de 1 y de sí mismo. Encuentra el mayor factor primo de n. Cuando n es primo, devuelve n.
Implementa largest_prime_factor(n).
Entrada
n: El entero a factorizar.
Salida
Devuelve su mayor divisor primo.
Restricciones
2 ≤ n ≤ 10¹². La entrada 1 está excluida porque no tiene factores primos.
Ejemplos
Entrada:
n = 84
Salida esperada:
expected = 7Entrada:
long long n = 84;
Salida esperada:
long long expected = 7;Entrada:
long n = 84;
Salida esperada:
long expected = 7;Explicación
84 = 2 × 2 × 3 × 7, así que el mayor factor primo es 7.
Entrada:
n = 13
Salida esperada:
expected = 13Entrada:
long long n = 13;
Salida esperada:
long long expected = 13;Entrada:
long n = 13;
Salida esperada:
long expected = 13;Explicación
13 es primo, así que es su propio mayor factor primo.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Quita primero los factores primos pequeños; cualquier valor restante solo puede disminuir, y el último factor que quede es la respuesta.
Pista 2
Prueba divisores solo hasta la raíz cuadrada del resto actual, y divídelo repetidamente cuando encaje.
Pista 3
Si el resto sigue siendo mayor que 1 después de revisar los factores menores, ese resto es primo y es el mayor factor.
Complejidad esperada
tiempo O(√n), espacio extra O(1)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.