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. 

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

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

Función main

Iniciamos el análisis con la función principal, esta función será la misma para las tres versiones que analizaremos para la descomposición de factores primos. Esta función 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 la función principal y no la función \texttt{descomponer\_factores}.

#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;
} 

Versión usando divisiones sucesivas

Analizaremos la primera versión del algoritmo para descomponer factores en C. 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. 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{do\ 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.

void descomponer_factores(int n) {
    do {
        
    } 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}.

void descomponer_factores(int n) {
    int factor_primo = 2;
    do {
        if (n % factor_primo == 0) {
            n /= factor_primo;
        }
    } while (n > 1);
} 

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.

void descomponer_factores(int n) {
    int factor_primo = 2;
    do {
        if (n % factor_primo == 0) {
            n /= factor_primo;
        } else
            factor_primo++;
    } while (n > 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{1}.

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

void descomponer_factores(int n) {
    printf("%d = ", n);
    int factor_primo = 2;
    int primer_factor = 1;
    do {
        if (n % factor_primo == 0) {
            if (primer_factor) {
                printf("%d", factor_primo);
                primer_factor = 0;
            } else
                printf("x%d", factor_primo);
            n /= factor_primo;
        } else
            factor_primo++;
    } while (n > 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}.

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

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 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.

int siguiente_primo(int n) {
    do {
        n++;
    } while (!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 C en donde analizamos seis diferentes versiones que permiten determinar si un número es primo o no.

int es_primo(int n) {
    if (n <= 1)
        return 0;
    int encontro_divisores = 0;
    int i = 2;
    while (i <= sqrt(n) && !encontro_divisores) {
        if (n % i == 0)
            encontro_divisores = 1;
        i++;
    }
    return !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}.

void descomponer_factores(int n) {
    printf("%d = ", n);
    int factor_primo = 2;
    int cant_factores = 0;
    int primer_factor = 1;
    do {
        if (n % factor_primo == 0) {
            cant_factores++;
            n /= factor_primo;
        } else {
            escribe_factor(&primer_factor, factor_primo, &cant_factores);
            factor_primo = siguiente_primo(factor_primo);
        }
    } while (n > 1);
    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{0} no se imprime la \texttt{x} pero se actualiza con el valor de \texttt{1} 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{1}, \texttt{factor\_primo} fuera 2 y \texttt{cant\_factores} fuera 3, se imprimiría 2^3.
  • Si \texttt{primer\_factor} fuera \texttt{0}, \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{0}, \texttt{factor\_primo} fuera 2 y \texttt{cant\_factores} fuera 1, se imprimiría \times 2. En este caso no se imprime el exponente.
void escribe_factor(int *primer_factor, int factor_primo, int *cant_factores) {
    if (*cant_factores > 0) {
        if (!*primer_factor)
            printf("x");
        else
            *primer_factor = 0;
        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 *