Descomposición en factores primos en C

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 ANSI C. Si deseas ver el enunciado del problema, haz click en el siguiente enlace. Si deseas entender el diseño algorítmico detrás de las soluciones presentadas, te invitamos a visitar el siguiente enlace.

Este ejercicio 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 ciertas funciones listas y las usaremos, luego nos preocuparemos de su implementación.

Función main

Iniciamos con la función main. Esta función 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 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. Esa responsabilidad es de la función 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 función.

#include <stdio.h>

void descomponer_factores(int n);

int main() {
    int n;
    printf("Ingrese un número (>1): ");
    scanf("%d", &n);

    if (n <= 1)
        printf("Debe ingresar un número mayor que uno\n");
    else
        descomponer_factores(n);
    return 0;
} 

Descomposición de factores

Ahora procedemos a implementar 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, es de tipo \texttt{void}, 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 esta función.

Control de flujo

La función \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

Se ha utilizado 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á. 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{do-while}. 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}

void descomponer_factores(int n) {
    int productoria = 1;
    do {        

    } while (productoria != n);
} 

Generación de posibles factores primos

Procederemos ahora a la generación de los posibles factores primos. Los candidatos a factores primos 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. Como estamos usando la técnica de diseño descendente, no nos preocuparemos en este momento cómo se hace esto. Asumiremos que existe una función llamada \texttt{siguiente\_primo} que se encarga de esto. 

El siguiente punto es determinar si efectivamente el número primo es un factor primo. Para esto verificamos si el resto de \texttt{n} entre \texttt{factor\_primo} retorna 0, si es así será un factor primo. 

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 de la función, 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.

void descomponer_factores(int n) {
    int productoria = 1;
    int copia_n = n;
    int factor_primo = 2;
    do {        
        int resto = copia_n % factor_primo;                
        if (resto == 0) {

        } else
            factor_primo = siguiente_primo(factor_primo);
    } while (productoria != n);
} 

Determinación del factor primo

Procederemos ahora a determinar el factor primo. Si el resto de \texttt{copia\_n} entre \texttt{factor\_primo} retorna \texttt{0}, pues hemos encontrado un factor primo. Procedemos a imprimirlo y luego actualizamos \texttt{copia\_n} con el cociente entero de \texttt{copia\_n} entre \texttt{factor\_primo}

Para calcular el resto usamos el operador de módulo que en ANSI C es \texttt{\%}. Para obtener el cociente entero, usamos la operación de asignación \texttt{/=}. Recuerde que \texttt{copia\_n/=factor\_primo} equivale a \texttt{copia\_n=copia\_n/factor\_primo}. Al ser ambos operandos enteros, la división que se realizará será entera.

void descomponer_factores(int n) {
    int productoria = 1;
    int copia_n = n;
    int factor_primo = 2;
    do {        
        int resto = copia_n % factor_primo;                
        if (resto == 0) {
            printf("%d", factor_primo);
            copia_n /= factor_primo;
        } else
            factor_primo = siguiente_primo(factor_primo);
    } while (productoria != n);
} 

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.

void descomponer_factores(int n) {
    int productoria = 1;
    int copia_n = n;
    int factor_primo = 2;
    do {        
        int resto = copia_n % factor_primo;                
        if (resto == 0) {
            if (productoria > 1)
                printf("x");
            printf("%d", factor_primo);
            copia_n /= factor_primo;
            productoria *= factor_primo;
        } else
            factor_primo = siguiente_primo(factor_primo);
    } while (productoria != n);
} 

Siguiente primo

La siguiente función a implementar es \texttt{siguiente\_primo}. 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. Asumimos que existe un módulo llamado \texttt{es\_primo} que se encarga de verificar si un número es primo o no.

int siguiente_primo(int n) {
    do {
        n++;
    } while (!es_primo(n));
    return n;
} 

Verifica primo

Finalmente, implementaremos la función \texttt{es\_primo}. Esta función retornará \texttt{1} si el número es primo y \texttt{0} 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

int es_primo(int n) {
    if (n <= 0)
        return 0;
    int cant_divisores = 0;
    int encontro_divisores = 0;
    int limite = sqrt(n);
    int i = 2;
    while (i <= limite && !encontro_divisores) {
        if (n % i == 0) {
            cant_divisores++;
            encontro_divisores = 1;
        }
        i++;
    }
    if (cant_divisores > 0 || n == 1)
        return 0;
    return 1;
} 

Descomposición de factores: versión alternativa 1

En la versión anterior de la función \texttt{descomponer\_factores}, 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.

void descomponer_factores(int n) {
    int productoria = 1;
    int copia_n = n;
    int factor_primo = 2;
    int cant_factores = 0;
    int hay_factores = 0;
    do {
        int resto = copia_n % factor_primo;
        if (resto == 0) {
            copia_n /= factor_primo;
            productoria *= factor_primo;
            cant_factores++;
        } else {
            if (cant_factores > 0) {
                if (hay_factores)
                    printf("x");
                else
                    hay_factores = 1;
                if (cant_factores == 1)
                    printf("%d", factor_primo);
                else
                    printf("%d^%d", factor_primo, cant_factores);
                cant_factores = 0;
            }
            factor_primo = siguiente_primo(factor_primo);
        }
    } while (productoria != n);
    if (hay_factores)
        printf("x");
    if (cant_factores == 1)
        printf("%d", factor_primo);
    else
        printf("%d^%d", factor_primo, cant_factores);
} 

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 la función se incrementa en tamaño. ¿Cómo solucionaremos este problema? Pues colocando el código repetido en una función aparte.

Contando factores

La versión de la función \texttt{descomponer\_factores} 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 a la función \texttt{escribe\_factor}.

void descomponer_factores(int n) {
    int productoria = 1;
    int copia_n = n;
    int factor_primo = 2;
    int cant_factores = 0;
    int hay_factores = 0;
    do {
        int resto = copia_n % factor_primo;
        if (resto == 0) {
            copia_n /= factor_primo;
            productoria *= factor_primo;
            cant_factores++;
        } else {
            escribe_factor(&hay_factores, factor_primo, &cant_factores);
            factor_primo = siguiente_primo(factor_primo);
        }
    } while (productoria != n);
    escribe_factor(&hay_factores, factor_primo, &cant_factores);
} 

Escribiendo factores

Esta 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{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. 
  • \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{\^ }). 
void escribe_factor(int *hay_factores, int factor_primo, int *cant_factores) {
    if (*cant_factores > 0) {
        if (*hay_factores)
            printf("x");
        else
            *hay_factores = 1;
        if (*cant_factores == 1)
            printf("%d", factor_primo);
        else
            printf("%d^%d", factor_primo, *cant_factores);
        *cant_factores = 0;
    }
} 

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 ANSI C. 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 quieres profundizar en el lenguaje ANSI C, no hay mejor libro que C Programming Language de Brian Kernighan  y Dennis Ritchie. Es un libro clásico escrito por el creador del lenguaje C. Uno de los libros favoritos de los que inician en ANSI C es  C Programming Absolute Beginner’s Guide de Greg Perry y Dean Miller.

Deja una respuesta

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