Factorización en Python

Esta entrada del blog pertenece a una serie:

• Números primos en Python
• Factorización en Python
• Máximo común divisor (MCD) en Python
• Mínimo común múltiplo (mcm) en Python

La factorización o descomposición en factores primos nos permite, dado un entero positivo, encontrar los números primos que multiplicados entre si nos den el número analizado. Por ejemplo, el número 33.880 se puede expresar como el producto de los siguientes números primos:

33880   =   2 x 2 x 2 x 5 x 7 x 11 x 11   =   2³ x 5 x 7 x 11²

A este proceso también se le conoce como descomposición factorial.

• Código en Repl.it

Descomposición factorial de un número

En Python podemos utilizar el siguiente código para conseguir descomponer números enteros positivos.

#!/bin/python3
# Descomposición en factores primos

def factoring(n): #descomposición en factores primos
  text= str(n) + ' = '
  i = 1
  for i in range(1, int(n/2)+1, 2):      # recorre los impares
    if i==1: i=2                         # salvo el 1 que será 2
    counter = 0
    while n % i == 0:
      n /= i
      counter += 1
    if counter == 1:
      text += str(i)+ ' × '
    elif counter > 1:
      text += str(i) + '^' + str (counter) + ' × '
  if text[-2] == "=":       # si no hay divisores
    text += str(n) + ' × '  # en ese caso el propio n será primo
  text += '1'
  return text

if __name__ == "__main__":
  while True:
    try:
      n = int(input('Introduzca el número a factorizar: ') or 202)
      if 1 < n <= 1e10:
        break
      else:
        print('Por favor, introduzca un número en el rango [2,10_000_000_000]')
    except ValueError:
      print('Por favor itroduzca un número entero positivo.')

  print(factoring(n))

Se basa en ir dividiendo sucesivamente primero entre 2, hasta que no sea divisible, luego entre 3 hasta que no sea divisible, y así con todos los números siguientes. Si bien, sabemos que si ya hemos dividido entre 2 todo lo posible, el número analizado no será divisible entre 4, por lo que podríamos saltar el 4. Esto es, únicamente tendríamos que dividir entre los primos menores al número analizado. Pero esto nos obligaría a ir calculando previamente los primos, por lo que optamos por dividir entre 2 y entre todos los impares menores que el número analizado.

Hemos solicitado factorizar el número 4.379.695.320 y el resultado que hemos obtenido es:

4379695320 = 2^3 × 3 × 5 × 7 × 11 × 13 × 19^2 × 101 × 1

Factorizar una serie de números

En este caso hemos adaptado el código anterior para poder aplicar la descomposición en factores primos a un rango de números.

#!/bin/python3  
# Descomposición en factores primos  
def factoring(n): #descomposición en factores primos  
  global r  
  r=1 # r es el resultado (variable global), sirve para comprobar que al final se cumple que r = n  
  text= str(n) + ' = '  
  for i in range(1,n+1,2):      # recorre los impares  
    if i==1: i=2          # salvo el 1 que será 2  
    counter = 0  
    while n%i == 0:  
      n /= i  
      r *= i           # el resultado r al final ha de coincidir con n. El valor de r se forma multiplicando los factores  
      counter+=1  
    if counter == 1:  
      text += str(i)+ ' × '  
    elif counter >1:  
      text += str(i) + '^' + str (counter) + ' × '  
  text += '1'  
  return text  
for j in range(2,20): # Descomposición en factores primos para los números comprendidos entre 2 y 19  
  text=factoring(j)  # Invocamos la función  
  print('{}  {}'.format(j==r, text))  # Si el número analizado coincide con el resultado r da True. r se obtiene multiplicando sus factores  
  if j!=r:  
    print('r = ',r)  
    break               # Si la comprobación da False se muestra el valor de r para ver el posible error.  

El valor True que figura en cada línea impresa indica que se ha pasado exitosamente la comprobación en la que el resultado r ha coincidido con el valor analizado en cada línea. El valor r se obtiene multiplicando todos los factores en los que hemos conseguido descomponer el número analizado.

Si lo desea, puede aumentar el rango para que llegue hasta 1.000 o más, y verá que, rápidamente, se llena su pantalla con todos los números sobre los que se va produciendo la descomposición en factores primos.