Factorización con números primos

Factorización con números primos

En matemática, factorizar un número entero implica descomponerlo en el producto de los números más pequeños posibles. Si se establece como condición que el producto esté compuesto únicamente por números primos, entonces se trata de una factorización con números primos. Algunos ejemplos de factorización con números primos:

  • Factorización de 12: 2 x 2 x 3.
  • Factorización de 36: 2 x 2 x 3 x 3.
  • Factorización de 144: 2 x 2 x 2 x 2 x 3 x 3.
  • Factorización de 147: 3 x 7 x 7.

El procedimiento para obtener los factores de un número n es el siguiente. Se toma el primer número primo, que es 2. Si n es divisible por 2, entonces 2 es el primer factor. Como ya encontramos el primer factor, ahora consideramos n como el cociente de la división anterior y volvemos a ejecutar el mismo procedimiento. Si n no es divisible por 2, se vuelve a intentar con el siguiente número primo, que es 3. Si n no es divisible por 3, se continua con el siguiente número primo, y así sucesivamente. El procedimiento termina cuando el cociente es 1.

Consideremos, por ejemplo, que nuestro n (o sea, el número que queremos factorizar) es 12. Tomamos el primer número primo, que es 2. ¿12 es divisible por 2? Sí, así que hacemos 12 / 2 y guardamos el cociente, que es 6. Ya tenemos nuestro primer factor: 2. Seguimos ahora con un nuevo n (6), el cociente de la división anterior, y repetimos el proceso. 6 es divisible por 2, de modo que ya tenemos nuestro segundo factor: también un 2. El cociente del paso anterior es 3 (6 / 2), que no es divisible por 2. Busquemos, entonces, el siguiente número primo: 3. 3 es divisible por 3, así que he aquí nuestro tercer factor: 3. Ya el cociente de la división anterior (3 / 3) es 1, por lo cual terminamos el procedimiento. Los factores que obtuvimos fueron 2, 2 y 3. De ahí que la factorización de 12 es igual a 2 x 2 x 3.

Veamos cómo implementarlo en Python. Primero, creemos una función que reciba como argumento un número para factorizar, al que llamaremos, aquí también, n.

def factorizar(n):

El primer paso del algoritmo, según vimos, es obtener el número primo más chico, que es 2. Pero si nuestro n no es divisible por 2, debemos continuar con el siguiente número primo, y así sucesivamente, lo cual implica que necesitaremos una forma de obtener los números primos. Tenemos un artículo que explica cómo generar números primos en Python; no obstante, a menos que queramos factorizar números demasiado grandes, es más conveniente crear manualmente una tupla de los primeros 10 números primos, que será suficiente en la mayoría de los casos.

def factorizar(n):
    numeros_primos = iter((2, 3, 5, 7, 11, 13, 17, 19, 23, 29))

Aquí creamos una tupla de números primos y la pasamos como argumento de iter() (una función incorporada que crea un objeto iterable) y asignamos el resultado a la variable numeros_primos. Un objeto iterable es como una colección (una lista o una tupla), pero del cual podemos consumir objetos a través de sucesivas llamadas a la función incorporada next(). Así, una primera llamada a next(numeros_primos) retorna 2, la segunda llamada retorna 3, la tercera retorna 5, y así hasta consumir todos los números de la tupla. Podemos comprobarlo en la consola interactiva:

>>> numeros_primos = iter((2, 3, 5, 7, 11, 13, 17, 19, 23, 29))
>>> next(numeros_primos)
2
>>> next(numeros_primos)
3
>>> next(numeros_primos)
5

Cuando todos los elementos de un objeto iterable han sido consumidos, next() lanza la excepción StopIteration.

Un objeto iterable de números primos es ideal para nuestro algoritmo de factorización, porque necesitamos consumir números primos para determinar si son divisores de n. En otros lenguajes que carecen de objetos iteradores uno típicamente crearía un contador i para acceder a los números primos, lo cual también sería válido en Python, aunque menos práctico.

Una vez que tenemos la lista de números primos, obtengamos el primer número:

def factorizar(n):
    numeros_primos = iter((2, 3, 5, 7, 11, 13, 17, 19, 23, 29))
    numero_primo_actual = next(numeros_primos)

Agreguemos, además, la creación de dos variables: resultado y cociente. La primera será la lista que contendrá los factores que vayamos encontrando y que finalmente constituirá el valor de retorno de nuestra función. La segunda almacenará el cociente de cada división.

def factorizar(n):
    numeros_primos = iter((2, 3, 5, 7, 11, 13, 17, 19, 23, 29))
    numero_primo_actual = next(numeros_primos)
    resultado = []
    cociente = None

Como aún no hemos realizado ninguna división, inicializamos el cociente como None. Ahora bien, sabemos que el procedimiento se detiene cuando el cociente es 1. Si el cociente no es 1, debemos repetir el procedimiento hasta llegar a ese valor. Indiquémosle a nuestra función que debe repetir el procedimiento mientras el cociente sea distinto de 1 con un bucle while.

def factorizar(n):
    numeros_primos = iter((2, 3, 5, 7, 11, 13, 17, 19, 23, 29))
    numero_primo_actual = next(numeros_primos)
    resultado = []
    cociente = None
    while cociente != 1:

Dentro del bucle debemos indicar lo que la función debe hacer con nuestro n. Ya tenemos el primer número primo en numero_primo_actual, así que averigüemos si n es divisible por numero_primo_actual. Para ello podemos usar el operador %, que obtiene el resto de una división. Así, si n % numero_primo_actual es igual a cero, quiere decir que el resto de n / numero_primo_actual es cero, por lo cual numero_primo_actual es divisor de n. Pero si el resto no es cero, eso indica que debemos seguir con el próximo número primo. Empecemos por esta última condición:

def factorizar(n):
    numeros_primos = iter((2, 3, 5, 7, 11, 13, 17, 19, 23, 29))
    numero_primo_actual = next(numeros_primos)
    resultado = []
    cociente = None
    while cociente != 1:
        if n % numero_primo_actual != 0:
            # No se puede dividir por este número primo,
            # obtener el siguiente y volver a ejecutar
            # el bucle.
            numero_primo_actual = next(numeros_primos)
            continue

Si numero_primo_actual es, por el contrario, divisor de n (o sea, si no se cumple la condición que establecimos en la línea 7), entonces tenemos nuestro primer factor que deberíamos agregar a la lista resultado.

def factorizar(n):
    numeros_primos = iter((2, 3, 5, 7, 11, 13, 17, 19, 23, 29))
    numero_primo_actual = next(numeros_primos)
    resultado = []
    cociente = None
    while cociente != 1:
        if n % numero_primo_actual != 0:
            # No se puede dividir por este número primo,
            # obtener el siguiente y volver a ejecutar
            # el bucle.
            numero_primo_actual = next(numeros_primos)
            continue
        resultado.append(numero_primo_actual)

Una vez agregado, nuestro n tiene que convertirse en el cociente de la división n / numero_primo_actual para que el procedimiento pueda continuar. Pero aún ni siquiera hemos ejecutado esa división ni le hemos dado un valor a la variable cociente que definimos originalmente como None. Hagamos todo eso en una línea:

def factorizar(n):
    numeros_primos = iter((2, 3, 5, 7, 11, 13, 17, 19, 23, 29))
    numero_primo_actual = next(numeros_primos)
    resultado = []
    cociente = None
    while cociente != 1:
        if n % numero_primo_actual != 0:
            # No se puede dividir por este número primo,
            # obtener el siguiente y volver a ejecutar
            # el bucle.
            numero_primo_actual = next(numeros_primos)
            continue
        resultado.append(numero_primo_actual)
        n = cociente = n / numero_primo_actual

Esta última línea, para evitar confusiones, es un atajo para:

        cociente = n / numero_primo_actual
        n = cociente

¡Listo! En cuanto el cociente se vuelva 1, el procedimiento terminará por sí mismo dado que hemos establecido que el bucle debe ejecutarse mientras (while) cociente != 1. Solo falta establecer el valor de retorno de la función:

def factorizar(n):
    numeros_primos = iter((2, 3, 5, 7, 11, 13, 17, 19, 23, 29))
    numero_primo_actual = next(numeros_primos)
    resultado = []
    cociente = None
    while cociente != 1:
        if n % numero_primo_actual != 0:
            # No se puede dividir por este número primo,
            # obtener el siguiente y volver a ejecutar
            # el bucle.
            numero_primo_actual = next(numeros_primos)
            continue
        resultado.append(numero_primo_actual)
        n = cociente = n / numero_primo_actual
    return resultado

Hagamos algunas pruebas debajo de esta definición:

print(factorizar(12))   # [2, 2, 3]
print(factorizar(36))   # [2, 2, 3, 3]  
print(factorizar(144))  # [2, 2, 2, 2, 3, 3]
print(factorizar(147))  # [3, 7, 7]

O bien solicitémosle al usuario que ingrese un número para factorizar:

n = int(input("Ingrese un número mayor a 1: "))
if n > 1:
    factores = factorizar(n)
    print(f"Factorización de {n}:", " x ".join(map(str, factores)))
else:
    print("Ingrese un número mayor a 1.")

Código completo:

def factorizar(n):
    numeros_primos = iter((2, 3, 5, 7, 11, 13, 17, 19, 23, 29))
    numero_primo_actual = next(numeros_primos)
    resultado = []
    cociente = None
    while cociente != 1:
        if n % numero_primo_actual != 0:
            # No se puede dividir por este número primo,
            # obtener el siguiente y volver a ejecutar
            # el bucle.
            numero_primo_actual = next(numeros_primos)
            continue
        resultado.append(numero_primo_actual)
        n = cociente = n / numero_primo_actual
    return resultado


n = int(input("Ingrese un número mayor a 1: "))
if n > 1:
    factores = factorizar(n)
    print(f"Factorización de {n}:", " x ".join(map(str, factores)))
else:
    print("Ingrese un número mayor a 1.")

Para las funciones join() y map(), véase 30 métodos de las cadenas y La función map().



Deja una respuesta