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. 

A continuación presentamos 2 alternativas de solución al problema de descomposición de un número en sus factores primos en PSeInt. Si deseas ver el enunciado del problema, haz click en el siguiente enlace

Este algoritmo lo resolveremos usando la técnica del diseño descendente. Empezaremos desde lo más general hasta lo más particular. En cada paso asumiremos que ya existen ciertos componentes y los usaremos, luego nos preocuparemos de su implementación.

Módulo principal

Iniciamos con el módulo principal. Este módulo básicamente realiza la lectura de datos, la validación de los datos de entrada y finalmente, invoca a la función \texttt{descomponer\_factores} para que haga la impresión de los factores primos.

En este punto, no nos interesa cómo se implementa \texttt{descomponer\_factores}, ese detalle se verá después, lo que importa 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. Esa función es del módulo principal y no del módulo \texttt{descomponer\_factores}.

Como estamos usando la técnica de diseño descendente, es importante tener claramente definidas las responsabilidades de cada módulo.

pseudocódigo descomposición de factores módulo principal
Módulo principal

Descomposición de factores

Ahora procedemos a implementar 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 usuarios el proceso de factorización. A continuación se explicará paso a paso cómo se ha construido este módulo.

Control de flujo

El módulo \texttt{descomponer\_factores} recibe el parámetro n que asumimos que debe ser mayor que uno. ¿Cómo imprimimos los factores primos del número n? Pues hay que buscarlos uno a uno. Debemos repetir este proceso hasta encontrar a todos los factores. Entonces queda claro que la estructura que debemos utilizar es una estructura iterativa. Hay dos cuestiones que resolver en relación a la estructura iterativa:

  1. ¿Qué tipo de estructura usamos? , ¿entrada controlada o salida controlada?
  2. ¿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 número 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? pues a través de una productoria. Iremos hallando los factores primos y los iremos multiplicando en la productoria. Cuando la productoria sea igual a n, la iteración deberá finalizar.

Usaremos la variable \texttt{productoria} para almacenar la productoria. La inicializamos con el valor de \texttt{1}. Utilizamos la estructura iterativa con salida controlada \texttt{Repetir-Mientras\ Que}. Esta instrucción repetirá el bloque de instrucciones tantas veces mientras la condición asociada es verdadera. Por este motivo usamos la condición \texttt{productoria<>n}

pseudocódigo descomposición de factores paso 1
Control de flujo

Generación de posibles factores primos

Procederemos ahora a la generación de los posibles factores primos. ¿Quiénes podrían ser los posibles factores primos de n? Pues, los candidatos van a ser todos los números primos que existen desde 2 hasta n. Lamentablemente no hay una fórmula matemática para poder calcular números primos  en un rango por lo que tendremos que buscarlos uno a uno.

Para este fin usaremos la variable \texttt{factor\_primo} la cual la inicializamos con el primer número primo conocido, es decir con el valor de 2. Una vez que se use, se actualizará con el siguiente número primo. Pero, ¿cómo obtenemos el siguiente número primo? No nos preocuparemos en este momento por el cómo sino que asumiremos que existe un módulo que ya realiza esto. Asumiremos que se llama \texttt{siguiente\_primo}. Recuerden que estamos usando la técnica de diseño descendente.

El siguiente punto es determinar si efectivamente el número primo es un factor primo. ¿Cómo hacemos esto? Muy simple, si el resto de \texttt{n} entre \texttt{factor\_primo} retorna 0, será un factor primo. Para este control usaremos una estructura selectiva doble.

Debemos tener en cuenta dos detalles. Una vez que hallemos el primer factor primo, debemos ahora actualizar \texttt{n} para hallar el próximo factor primo. Pero no podemos modificar \texttt{n} pues lo usamos en la condición de salida. Por este motivo, al inicio del algoritmo, hacemos una copia de n y lo almacenamos en la variable \texttt{copia\_n}. De esta forma, mantenemos el valor de \texttt{n} sin que cambien en nuestro algoritmo.

El otro detalle a considerar es que un número primo, puede ser un factor en más de una ocasión. Por este motivo no actualizamos inmediatamente nuestra variable \texttt{factor\_primo} sino que lo haremos cuando el \texttt{resto} sea diferente de cero. Esto permitirá hallar el factor primo tantas veces como sea necesario.

pseudocódigo descomposición de factores paso 2
Generación de posibles factores primos

Determinación del factor primo

Procederemos ahora a determinar el factor primo. Es importante que hayas entendido bien los pasos anteriores. De ser así continúa, en caso contrario, analiza al detalle el paso anterior. 

Si el resto de \texttt{copia\_n} entre \texttt{factor\_primo} retorna \texttt{0}, pues hemos encontrado un factor primo. ¿Qué hacemos? Pues procedemos a imprimirlo. Luego de imprimirlo, actualizamos \texttt{copia\_n} con el cociente entero de \texttt{copia\_n} entre \texttt{factor\_primo}. Como ven, \texttt{copia\_n} se modifica, si hubiéramos usado directamente el valor de \texttt{n}, nuestro diseño algorítmico fallaría.

Para calcular el resto usamos el operador de módulo que en PSeInt es \texttt{mod}. Para obtener el cociente entero, usamos la operación de división y al resultado, le aplicamos la función \texttt{trunc} que truncará el número, dejando solamente la parte entera.

pseudocódigo descomposición de factores paso 3
Determinación del factor primo

Actualización de la productoria

Para finalizar esta función, solo faltaría actualizar la productoria. Este paso es bastante simple, basta que multipliquemos la \texttt{productoria} por el \texttt{factor\_primo}. Teniendo cuidado de hacerlo si y solo si, el resto es cero.

Podemos ver que \texttt{productoria} tendrá un valor mayor que cero si es que en la iteración se ha encontrado un factor primo. Usaremos este conocimiento para imprimir el caracter \texttt{x} que representará a la multiplicación del factor. Haremos esto siempre, excepto la primera vez.

pseudocódigo descomposición de factores paso 4
Actualización de la productoria

Siguiente primo

El siguiente módulo a diseñar es el \texttt{siguiente\_primo}. Como comentamos anteriormente, no existe fórmula matemática para encontrar el siguiente primo dado un valor de \texttt{n}, por lo que deberemos usar la fuerza bruta. Es por este motivo que los números primos son usados en el algoritmo RSA para encriptar información.

El algoritmo es simple, 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

Verifica primo

Finalmente, diseñaremos el módulo \texttt{es\_primo}. Este módulo retornará \texttt{Verdadero} si el número es primo y \texttt{Falso} en caso contrario. Hemos analizado en un artículo en iterando++, 5 formas distintas de verificar si un número es primo, si deseas entender este algoritmo, te invitamos a revisar el siguiente enlace

pseudocódigo es primo
Verifica primo

Descomposición de factores: versión alternativa 1

En la versión anterior del algoritmo, los factores se imprimían uno a continuación de otro sin importar que se repitan o no. En esta versión se hace una variación para que en el caso de que se tenga un factor primo repetido, este aparezca una sola vez pero con el exponente. Representaremos el exponente con el símbolo \texttt{\^ }.

El principal cambio que tiene esta versión es que se ha introducido la variable \texttt{cant\_factores} que tiene como objetivo contar cuantos factores primos iguales tiene el número \texttt{n} para el \texttt{factor\_primo} que se está analizando. Se inicializa con el valor de \texttt{0} que semánticamente indica que no se ha encontrado ningún factor.

Cada vez que encontramos un factor primo, no lo imprimimos. En su lugar incrementamos la cantidad de factores. La impresión la realizaremos antes de buscar el siguiente número primo. Para esto verificamos si es que se encontraron factores (\texttt{cant\_factores>0}), si se verifica la condición se imprime el factor y si tiene más de uno, se imprime el exponente. Es de vital importancia que luego de imprimir el factor primo, la variable \texttt{cant\_factores} pase nuevamente a actualizarse con el valor de \texttt{0}.

Note que la misma lógica de impresión se debe colocar luego de la iteración. Eso es necesario para poder imprimir el último factor primo hallado.

pseudocódigo siguiente primo versión alternativa 1
Descomposición de factores: versión alternativa 1

Descomposición de factores: versión alternativa 2

La versión alternativa 1 resuelve el problema presentado en el enunciado pero tiene un problema. El código para la impresión de los factores primos se repite dentro de la iteración y fuera de la iteración. Dicha solución no es elegante. Además el algoritmo se incrementa en tamaño. ¿Cómo solucionaremos este problema? Pues colocando el código repetido en un módulo aparte.

Contando factores

La versión del módulo es muy similar a la versión 1, la única diferencia es que el código para escribir el factor no está, en su lugar hay una llamada al módulo \texttt{escribe\_factor}.

pseudocódigo siguiente primo versión alternativa 2 paso 1
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.
pseudocódigo siguiente primo versión alternativa 2 paso 2
Escribiendo 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 *