Algoritmos y Estructuras de Datos

Factorización en primos

Cualquier número entero positivo n ≥ 2 puede expresarse como un producto de números primos:
Existen numerosas aplicaciones para el hallazgo de factores primos cuando trabajamos con números. Entre otras cosas, nos permite contar fácilmente la cantidad de divisores de un número, también facilita la comprensión para calcular el máximo común divisor (GCD) y el mínimo común múltiplo (LCM) de dos números, etc.
Para representar un número n (por ejemplo 300) como un producto de sus factores primos, se puede comenzar con el menor número primo p (2) y, si n es divisible entre p, seguir dividiendo n por p mientras sea posible (300 / 2 = 150, 150 / 2 = 75).
Posteriormente se incrementa p en 1 (p = 3) y se intenta dividir n por el nuevo p. En caso de que sea posible, se divide n por p tantas veces como se pueda (75 / 3 = 25).
Luego se incrementa p en 1 de nuevo (p = 4) y se vuelve a intentar. No es posible dividir n por ningún número que no sea primo, dado que n ya se dividió exhaustivamente por primos más pequeños. En nuestro ejemplo, 300 sí es divisible por 4, pero 75 no lo es, debido a que dividimos 300 por 2 (divisor de 4) varias veces antes. Esto implica que, si ya hemos agotado todas las divisiones por 2, en el futuro no se podrá dividir por 4, 6, 8 ni por ningún múltiplo de 2. El hecho de avanzar desde el número más pequeño hasta el más grande garantiza que, al final, solo queden números primos que puedan dividir lo que resta de n.
En el siguiente paso, incrementamos nuevamente el divisor en 1 (p = 5) y probamos dividir n por el nuevo p (75 / 5 = 5, 5 / 5 = 1). Este proceso continúa hasta que el divisor sea mayor que . Si se llega a la situación en la cual el divisor es mayor que ⇒ entonces el n restante es un número primo, y se incluye como uno de los divisores en la respuesta final.
Por lo tanto, en nuestro ejemplo, 300 se puede representar como .
n = ...                              # Representar n como producto de primos
p, divisors, powers = 1, [], []      # prime factor, divisores, y sus exponentes

while p * p <= n:                    # mientras p <= sqrt(n)
    p += 1                           # Se le suma 1 al factor primo en cada iteración
    if n % p != 0:                   # No hacer nada si n no es divisible por p
        continue
    
    divisors.append(p)               # n % p == 0 => se agrega p como factor primo
    powers.append(0)                 # el exponente inicia en 0
    while n % p == 0:                # dividir tantas veces como sea posible
        n //= p
        powers[-1] += 1              # incrementar el exponente en cada iteración

if n > 1:                            # si p > sqrt(n) => n es un factor primo por sí mismo
    divisors.append(n)               # se agrega n como divisor
    powers.append(1)                 # con exponente 1

print(list(zip(divisors, powers)))   # imprimir factores y sus exponentes juntos
En cada iteración del algoritmo, se divide el número por su factor primo si es posible y se continúa dividiendo a la vez que se incrementa el exponente en cada paso.
Veamos una simulación del algoritmo con varios números:
n = 24
  1. p = 2, n = 24 (incrementamos p de 1 a 2 al inicio del ciclo)
  1. p = 3, n = 3 ⇒ se detiene el ciclo while porque p * p = 9, que es mayor que 3
  1. n > 1 ⇒ divisors = [2, 3], powers = [3, 1]
n = 75
  1. p = 2, n = 75
  1. p = 3, n = 75
  1. p = 4, n = 25
  1. p = 5, n = 25
  1. p * p > n ⇒ se detiene el ciclo while ⇒ divisors = [3, 5], powers = [1, 2]
n = 84
  1. p = 2, n = 84
  1. p = 3, n = 21
  1. p * p > n ⇒ se detiene el ciclo while
  1. n > 1 ⇒ divisors = [2, 3, 7], powers = [2, 1, 1]
n = 31
  1. p = 2, n = 31
  1. p = 3, n = 31
  1. p = 4, n = 31
  1. p = 5, n = 31
  1. p = 6, n = 31
  1. p * p > n ⇒ se detiene el ciclo while
  1. n > 1 ⇒ divisors = [31], powers = [1]

Desafío

Dado un número entero n, se pide encontrar su factor primo más grande.

Entrada

La primera línea de la entrada contiene un solo número entero n (2 ≤ n ≤ ).

Salida

El programa debe imprimir el factor primo más grande de n.

Ejemplos

Entrada
Salida
8
2
24
3
75
5
31
31
Bonus: ¿Por qué no comprobamos solo los números primos?
Nuestra implementación actual del algoritmo revisa todos los números 2, 3, 4, … hasta . ¿No tendría más sentido iterar únicamente sobre los números primos?
A primera vista, parece una buena idea (y podría haber casos donde esto funcione). Sin embargo, el proceso de hallar todos los números primos hasta llevaría más iteraciones que simplemente llegar a (para ser más precisos, ). Por tanto, hallar esos números primos sería más costoso que iterar por todos los posibles divisores hasta y verificar si n es divisible por cada uno.
¿Se te ocurre alguna situación en la que determinar de antemano todos los números primos y luego usarlos para factorizar pudiera ser más óptimo?
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue