Descomposición en factores primos en PSeInt

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 PSeInt. 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 PSeInt» en nuestro canal de YouTube. Te invitamos a que lo visites.

Analizaremos 3 algoritmos para descomponer factores en PSeInt. 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.

Módulo principal

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

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

factores_primos_pseudocodigo_módulo_principal
Módulo principal

Versión usando divisiones sucesivas

Analizaremos la primera versión del algoritmo para descomponer factores en PSeInt. En esta versión usaremos las divisiones sucesivas como mecanismo para encontar los factores primos. Todo esto se implementará en el módulo \texttt{descomponer\_factores}. Este módulo 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. El módulo 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 este módulo.

Control de iteración

El módulo \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. Sin embargo, hay dos cuestiones que resolver en relación a dicha estructura:

  • ¿Qué tipo de estructura usamos? , ¿entrada controlada o salida controlada?
  • ¿Cómo controlamos el flujo?

En relación al tipo de estructura iterativa a emplear, se ha decidido usar un ciclo iterativo con salida controlada. Esto pues sabemos que como n es mayor que uno, existirá por lo menos un factor primo que hallar. Por lo tanto la iteración debe hacerse por lo menos una vez. 

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 salida controlada \texttt{Repetir-Mientras\ Que}. 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.

factores_primos_pseudocodigo_divisiones_iteración
Control de iteración

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\ mod\ 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{trunc(n/factor\_primo)}. En la siguiente sección analizaremos como debemos actualizar la variable \texttt{factor\_primo}.

factores_primos_pseudocodigo_divisiones_control_de_flujo
Control de flujo

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.

factores_primos_pseudocodigo_divisiones_factores
Generación de posibles factores primos

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{Verdadero}.

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{Falso}, 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.

factores_primos_pseudocodigo_divisiones_impresión
Impresión del factor

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 el módulo \texttt{siguiente\_primo}.

factores_primos_pseudocodigo_version_primos
Factores primos usando verificación de nímeros primos

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 salida 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 este módulo por ello. Asumimos que existe un módulo llamado \texttt{es\_primo} que se encarga de verificar si un número es primo.

pseudocódigo siguiente primo
Siguiente primo

Verificando si un número es primo

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

factores_primos_pseudocodigo_verifica_primos
Verificación de un número primo

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 el módulo \texttt{escribe\_factor}.

imos_pseudocodigo_version_conteo
Versión contando factores

Escribiendo factores

El módulo \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{Falso} no se imprime la \texttt{x} pero se actualiza con el valor de \texttt{Verdadero} para que la impresión se realice en la siguiente llamada. Es parámetro por referencia. 
  • \texttt{factor\_primo} indica el factor primo que se imprimirá. Es parámetro por valor.
  • \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{\^ }). Es parámetro por referencia.
 
Por ejemplo:
  • Si \texttt{primer\_factor} fuera \texttt{Verdadero}, \texttt{factor\_primo} fuera 2 y \texttt{cant\_factores} fuera 3, se imprimiría 2^3.
  • Si \texttt{primer\_factor} fuera \texttt{Falso}, \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{Falso}, \texttt{factor\_primo} fuera 2 y \texttt{cant\_factores} fuera 1, se imprimiría \times 2. En este caso no se imprime el exponente.
factores_primos_pseudocodigo_version_conteo_escribe_factor
Escribiendo los 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 PSeInt. 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 en lenguajes de programación. Te invitamos a leer los siguientes artículos de iterando++

Si te interesa profundizar más sobre diseño algorítmico, te recomendamos el libro Foundations of Programming Languages de Kent D. D. Lee. En este libro encontrarás además información detallada sobre la programación orientada a objetos, funcional y lógica.

Deja una respuesta

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