Todos los desafíos
Intermedio 2 resueltos 28.6% de aceptación

Mayor Factor Primo

Encuentra el mayor número primo que divide a un entero positivo.

Lo que aprenderás

  • Dividir los factores del menor al mayor
  • Parar en la raíz cuadrada de lo que queda
  • Manejar números grandes con eficiencia

Problema

Ver original (inglés)

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

Ejemplo 1
Entrada:
n = 84

Salida esperada:
expected = 7
Entrada:
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.

Ejemplo 2
Entrada:
n = 13

Salida esperada:
expected = 13
Entrada:
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.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

# Programador Lenguaje Tiempo Memoria Revisión de IA Solución
1 ННикита Python 949 ms - 4/5 Ver código
2 KKKaneki Ken Python 1,000 ms - 3/5 Ver código

Aprende de otros

Soluciones de la comunidad

Alerta de spoiler: 2 soluciones completas abajo Intenta resolverlo tú mismo primero. Igual puedes ver el código de otros desarrolladores y las reseñas de IA. Inicia sesión y resuelve el reto para unirte a la discusión.