Descomposición en factores primos en Python

Más ejercicios resueltos

Si deseas revisar más ejercicios resueltos, haz click en el siguiente botón. 

La factorización es el proceso de representar una expresión algebraica, como por ejemplo un número, en forma de producto los cuales son llamados factores. En esta entrada presentamos 3 algoritmos que nos permitirán descomponer un número en sus factores primos en Python. Al final de esta página encontrarás un enlace para poder descargar los algoritmos analizados. Si deseas ver el enunciado del problema, haz click en el siguiente enlace

Parte de este análisis se encuentra sintetizado en el vídeo «Descomposición en Factores Primos en Python» en nuestro canal de YouTube. Te invitamos a que lo visites.

Analizaremos 3 algoritmos para descomponer factores en Python. Cada algoritmo será analizado desde el punto de vista del pensamiento computacional y usando la técnica del diseño descendente. Las versiones de los algoritmos que serán analizadas serán las siguientes:

  • Versión usando divisiones sucesivas.
  • Versión usando números primos.
  • Versión contando los factores primos.

Programa principal

Iniciamos el análisis con el programa principal, este programa será el mismo para las tres versiones que analizaremos para la descomposición de factores primos. Este programa básicamente realiza la lectura de datos, la validación de los datos de entrada y finalmente, la invocación a la función \texttt{descomponer\_factores} para que haga la impresión de los factores primos.

En este punto, no nos interesa analizar cómo se implementa la función \texttt{descomponer\_factores}, ese detalle lo veremos más adelante, lo que importa conocer en este punto es qué hace dicha función. Dicha función se encargará de imprimir los factores primos dado un número natural n. Esta función tiene como precondición que dicho número n sea mayor que 1. Al momento de invocarla, debemos garantizar que esta precondición se cumpla, esta responsabilidad la tiene el programa principal y no la función \texttt{descomponer\_factores}.

n=int(input("Ingrese un número (>1): "))
if n <= 1:
    print("Debe ingresar un número mayor que uno")
else:
    descomponer_factores(n) 

Versión usando divisiones sucesivas

Analizaremos la primera versión del algoritmo para descomponer factores en Python. En esta versión usaremos las divisiones sucesivas como mecanismo para encontar los factores primos. Todo esto se implementará en la función \texttt{descomponer\_factores}. Esta función buscará todos los factores primos del número en cuestión y los presentará al usuario. Recibe como parámetro n que representa el número que queremos descomponer. La función no retorna ningún valor, básicamente se dedica a presentar al usuario el proceso de factorización. A continuación se explicará paso a paso cómo se ha construido esta función.

Control de iteración

La función \texttt{descomponer\_factores} recibe el parámetro n que asumimos que debe ser mayor a uno. Pero, ¿cómo imprimir los factores primos del número n? Pues hay que buscarlos uno a uno. Debemos repetir la búsqueda hasta encontrar a todos los factores primos del número en cuestión. Queda claro que la estructura que debemos utilizar es una estructura iterativa. 

En relación al tipo de estructura iterativa a emplear, se usará un ciclo iterativo con entrada controlada. En relación al control de flujo, este problema es un caso peculiar y debemos analizarlo con sumo detalle. No es la típica iteración en donde sabemos la cantidad de veces que se repetirá, tampoco podemos colocar una condición clásica como \texttt{i<n}. Entonces, ¿cómo controlamos la iteración? Analizaremos en este punto las divisiones sucesivas. Dado un número cualquiera, al dividirlo entre todos sus factores primos, el resultado final será siempre 1. Por lo tanto, usaremos este hecho para controlar la iteración.

Utilizamos la estructura iterativa con entrada controlada \texttt{while}. Esta instrucción repetirá el bloque de instrucciones tantas veces mientras que la condición asociada sea verdadera. Por este motivo usamos la condición \texttt{n>1}. Cada vez que hallamos un factor primo, procederemos a dividir el número \texttt{n} entre el factor primo hallado.

def descomponer_factores(n):   
    while n>1:
 

Control de flujo

En esta sección analizamos el control de flujo de la iteración que nos permitirá descomponer un número en sus factores primos. Ya hemos visto que la condición de la iteración es \texttt{n>1}, esto debido a que realizaremos divisiones sucesivas, pero, ¿entre qué valores vamos a dividir el número \texttt{n}? Pues entre los factores primos de \texttt{n}. Por lo tanto, debemos comenzar a buscar estos factores primos.

Para esto usaremos la variable \texttt{factor\_primo}, el objetivo de esta variable es almacenar los posibles factores primos del número \texttt{n}. Iremos actualizando esta variable hasta que contenga un factor primo del número pasado como parámetro. Para esto la inicializamos con el valor de \texttt{2} que es el primer número primo.

Para determinar si el valor contenido en esta variable es efectivamente un factor primo del número, el resto de la división entera del número entre la variable \texttt{factor\_primo} debe ser igual a cero. Por este motivo en la iteración verificamos esto a través de una estructura algorítmica selectiva usando la condición \texttt{n\ \%\ factor\_primo==0}.

Cuando encontramos un factor primo, procedemos a actualizar el número con el resultado de la división del número entre el factor primo, para ello usamos la expresión \texttt{n\ //=\ factor\_primo}. En la siguiente sección analizaremos como debemos actualizar la variable \texttt{factor\_primo}.

def descomponer_factores(n):   
    factor_primo = 2
    while n>1:
        if n % factor_primo == 0:
            n //= factor_primo             

Generación de posibles factores primos

¿Cómo generamos el siguiente factor primo? Pues en este caso lo que haremos será probar con los siguientes números naturales, razón por la cual incrementamos en uno a la variable \texttt{factor\_primo}. Pero, ¿no se supone que los factores primos son números primos?, entonces, ¿cómo garantizamos que efectivamente se encuentren números primos? Lo que sucede es que para determinar si el valor contenido en la variable \texttt{factor\_primo} es efectivamente un factor primo de n verificamos que no exista resto al dividir al número entre el factor. Como comenzamos desde 2 y dividimos sucesivamente el número n entre 2, garantizamos que ya no sea posible dividirlo por ningún múltiplo de 2. Luego continuamos con 3,  y así sucesivamente. De forma tal que aunque incrementamos \texttt{factor\_primo} en uno, solamente serán factores los números primos.

def descomponer_factores(n):   
    factor_primo = 2
    while n>1:
        if n % factor_primo == 0:
            n //= factor_primo            
        else:  
            factor_primo += 1  

Impresión del factor primo

Analizaremos ahora la impresión de los factores primos. La primera línea de código se encargará de imprimir el número n seguido del carácter igual. 

Analicemos los factores primos del número 60. El número 60 expresado en sus factores primos se puede escribir como 2 \times 2 \times 3 \times 5 . Podemos notar que la impresión inicia con 2, luego con \times 2, luego con \times 3 y finalmente con \times 5. El único factor que no viene precedido del carácter de multiplicación es el primero. Es por este motivo que el algoritmo debe saber si el factor que se imprimirá será el primero o no. Para esto usamos la variable \texttt{primer\_factor} la cual la inicializamos con el valor de \texttt{True}.

Esta variable la usaremos siempre que encontremos un factor primo del número, en caso sea el primer factor, imprimiremos únicamente el número y luego actualizamos la variable \texttt{primer\_factor} con el valor de \texttt{False}, de esta manera el algoritmo sabrá que ya se imprimió el primer factor. En caso no nos encontremos imprimiendo el primer factor, procederemos a imprimir el factor primo, pero le anteponemos el carácter \times.

def descomponer_factores(n):   
    print(n," = ", end="") 
    factor_primo = 2
    primer_factor = True
    while n>1:
        if n % factor_primo == 0:
            if primer_factor:
                primer_factor = False
            else:
                print("x", end="")
            print(factor_primo, end="")
            n //= factor_primo            
        else:  
            factor_primo += 1  

Versión usando números primos

Veremos ahora la segunda alternativa de solución. Es en esencia muy similar a la anterior, pero en lugar de incrementar en uno a la variable \texttt{factor\_primo}, la actualizaremos con el siguiente número primo pues es así en realidad como se realiza la descomposición en factores primos. Usaremos para ello la función \texttt{siguiente\_primo}.

def descomponer_factores(n): 
    print(n," = ", end="")    
    factor_primo = 2
    primer_factor = True
    while n>1:
        if n % factor_primo == 0:
            if primer_factor:
                primer_factor = False
            else:
                print("x", end="")
            print(factor_primo, end="")
            n //= factor_primo            
        else:  
            factor_primo = siguiente_primo(factor_primo)  

Buscando el siguiente número primo

Pero, ¿cómo se puede obtener el siguiente número primo dado un número primo cualquiera? Dado que no existe una fórmula para generar números primos, la única manera de obtener el siguiente primo es ir generando números consecutivos y verificar si son primo. Usaremos para ello una estructura iterativa con entrada controlada.

El algoritmo usado es simple de entender, usamos una iteración y lo que hacemos es incrementar el valor de \texttt{n} en 1 mientras \texttt{n} no sea un número primo. ¿Cómo verificamos si un número es primo? Pues no nos preocupamos en esta función por ello. Asumimos que existe una función llamada \texttt{es\_primo} que se encarga de verificar si un número es primo.

def siguiente_primo(n):
    while True:
        n+=1
        if es_primo(n):
            return n 

Verificando si un número es primo

Para verificar si un número es primo usaremos la función \texttt{es\_primo}. Esta función se ha implementado usando la estrategia denominada búsqueda de divisores. Si te interesa analizar con más detalle esta función te invitamos a que visites luego nuestro artículo Verificación de números primos en Python en donde analizamos seis diferentes versiones que permiten determinar si un número es primo o no.

def es_primo(n):
    if n <= 1:
        return False
    encontro_divisores = False    
    i = 2
    while i <= math.sqrt(n) and not encontro_divisores:
        if n % i == 0:
            encontro_divisores = True
        i+=1    
    return not encontro_divisores 

Versión contando los factores

Contando factores

Finalmente analizaremos la tercera solución. Esta solución se basa en el conteo de factores. Hasta el momento hemos realizado la descomposición de factores primos y hemos impreso dicha descomposición como el producto de cada factor, sin importar si este se repite o no. Así, por ejemplo, el número 60 lo podemos escribir como 2 \times 2 \times 3 \times 5, pero el mismo se podría escribir como 2^2 \times 3 \times 5. En este caso, como el 2 se multiplica dos veces, lo escribimos como 2 elevado al cuadrado. Esta forma de escribir es la más común en el mundo de las matemáticas.

Para este fin, incluimos la variable \texttt{cant\_factores} que indicará cuantos factores iguales existen. Al inicio esta variable la inicializamos con el valor de cero. Cada vez que encontramos un factor primo, no lo imprimimos como en las versiones anteriores, sino que incrementamos el contador en 1.

Pero, si nos dedicamos a contar, entonces ¿cuándo realizamos la impresión? Pues antes de actualizar el próximo factor primo, nos dedicamos a realizar la impresión. Note que también debemos hacer la impresión también luego del ciclo iterativo para poder imprimir el último factor del número. Esto debido a que contamos e imprimimos en momentos diferentes. La impresión la realizamos en la función \texttt{escribe\_factor}.

def descomponer_factores(n): 
    print(n," = ", end="")    
    factor_primo = 2
    primer_factor = True
    cant_factores = 0
    while n>1:
        if n % factor_primo == 0:
            cant_factores += 1
            n //= factor_primo            
        else:  
            primer_factor, cant_factores = escribe_factor(primer_factor, factor_primo, cant_factores)
            factor_primo = siguiente_primo(factor_primo)  
    primer_factor, cant_factores = escribe_factor(primer_factor, factor_primo, cant_factores) 

Escribiendo factores

La función \texttt{escribe\_factor} tiene como objetivo escribir el factor en cuestión. Posee 3 parámetros:

  •  \texttt{hay\_factores} indica si es que antes del factor que se está imprimiendo, ya se había impreso un factor. Esto permitirá imprimir el caracter \texttt{x} que simboliza la multiplicación. Si este valor es \texttt{False} no se imprime la \texttt{x} pero se actualiza con el valor de \texttt{True} para que la impresión se realice en la siguiente llamada.  
  • \texttt{factor\_primo} indica el factor primo que se imprimirá.  
  • \texttt{cant\_factores} indica la cantidad de factores que se van a imprimir. Este valor sirve para que el algoritmo decida si es que se imprime o no el exponente (\texttt{\^ }).  
 
Por ejemplo:
  • Si \texttt{primer\_factor} fuera \texttt{True}, \texttt{factor\_primo} fuera 2 y \texttt{cant\_factores} fuera 3, se imprimiría 2^3.
  • Si \texttt{primer\_factor} fuera \texttt{False}, \texttt{factor\_primo} fuera 2 y \texttt{cant\_factores} fuera 3, se imprimiría \times 2^3. En este caso se ha añadido el símbolo de multiplicación dado que ya se ha impreso el primer factor anteriormente.
  • Si \texttt{primer\_factor} fuera \texttt{False}, \texttt{factor\_primo} fuera 2 y \texttt{cant\_factores} fuera 1, se imprimiría \times 2. En este caso no se imprime el exponente.
def escribe_factor(primer_factor, factor_primo, cant_factores):
    if cant_factores > 0:
        if primer_factor:
            primer_factor = False
        else:
             print("x", end="")
        if cant_factores==1:
            print(factor_primo, end="")
        else:
            print("{:d}^{:d}".format(factor_primo, cant_factores), end="")      
        cant_factores = 0        
    return primer_factor, cant_factores  

Conclusión

Hemos presentado en este artículo, una propuesta de solución a la descomposición de un número en sus factores primos usando Python. Se ha utilizado para el diseño algorítmico la técnica del diseño descendente y se ha controlado  el flujo en los módulos usando estructuras selectivas e iterativas. Podrá descargar la solución propuesta en el repositorio GitHub de iterando++ a través del siguiente enlace

Hemos preparado otros artículos adicionales en donde describimos al detalle la implementación de este problema PSeInt y en otros lenguajes de programación. Te invitamos a leer los siguientes artículos de iterando++

Si te interesa profundizar más en el desarrollo en Python, los dos mejores libros que se han escrito son Learning Python de Mark Lutz y Python Crash Course de Eric Matthes.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *