Factoriza un número en primos

Veamos como factorizar un número en sus primos. Es decir, cualquier número que se te ocurra puede ser expresado como la multiplicación de varios números primos.

• El 8 es 2*2*2.
• El 765 es 3*3*5*17.

Este tipo de factorización es muy interesante porque permitiría romper los algoritmos de criptografía actuales. Sin embargo para números muy grandes es tan complicado encontrar la solución que en la práctica es imposible.

Podemos definir la función de la siguiente manera. Intenta dividir nuestro número n por todos los números posibles, empezando por el 2. Si es divisible por divisor, lo almacenamos como factor y continuamos con el siguiente.

def factorizar(n):
    factores = []

    for divisor in range(2, int(n**0.5) + 1):
        while n % divisor == 0:
            factores.append(divisor)
            n //= divisor
    
    if n > 1:
        factores.append(n)
    return factores

Veamos un ejemplo factorizando 765.

numero = 765
factores = factorizar(numero)
print(f"{numero} = {'*'.join(map(str, factores))}")
# 765 = 3*3*5*17

Ahora, un ejemplo con un número mayor. Como puedes ver, a medida que el número es más grande, más tiempo se tarda en factorizar.

numero = 10000004400000259
factores = factorizar(numero)
print(f"{numero} = {'*'.join(map(str, factores))}")
# 10000004400000259 = 100000007*100000037

✏️ Ejercicios:

• Busca un número no sea posible factorizar porque tarde demasiado tiempo.