martes, 19 de enero de 2021

Factorización 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   =   23 x 5 x 7 x 112

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

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) + ' = '  
  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  
      counter+=1  
    if counter == 1:  
      text += str(i)+ ' × '  
    elif counter >1:  
      text += str(i) + '^' + str (counter) + ' × '  
  text += '1'  
  return text  
  
if __name__ == "__main__":  
  while True:  
    try:  
      n=int(input('Introduzca el número a factorizar: ') or 33880) # por defecto, al pulsar ENTER se usa el número 33880  
      if 1<n<=1e10:  
        break  
      else:  
        print('Por favor, introduzca un número en el rango [2,10000000000]')  
    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.