Descomposición en factores primos en Java

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 Java. 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 ciertos métodos listos y los usaremos, luego nos preocuparemos de su implementación.

Método principal

Iniciamos con el método principal. Este método básicamente realiza la lectura de datos, la validación de los datos de entrada y finalmente, invoca al método \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étodo. Dicho método se encargará de imprimir los factores primos dado un número natural n. Este método 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 responsabilidad es del método principal y no del método \texttt{descomponer\_factores}.

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

package descomposicion_factores_primos_v1;

import java.util.Scanner;

public class Descomposicion_factores_primos_v1 {

    public static void main(String[] args) {
        int n;
        Scanner reader = new Scanner(System.in);
        System.out.printf("Ingrese un número (>1): ");
        n = reader.nextInt();

        if (n <= 1) {
            System.out.printf("Debe ingresar un número mayor que uno%n");
        } else {
            descomponer_factores(n);
        }
    }
} 

Descomposición de factores

Ahora procedemos a implementar el método \texttt{descomponer\_factores}. Este método 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étodo no retorna ningún valor, es de tipo \texttt{void}, básicamente se dedica a presentar al usuarios el proceso de factorización.

Recuerde que \texttt{private} es un modificador de acceso que especifica que el método no se puede invocar fuera de la clase. Por su lado, la directiva \texttt{static}, define al método como estático, lo que significa que se puede invocar al método sin tener que instanciar un objeto de la clase.  A continuación se explicará paso a paso cómo se ha construido este método.

Control de flujo

El método \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}

    private static 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 un método llamado \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 del método, 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.

    private static 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 Java 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.

    private static 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) {
                System.out.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.

    private static 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) {
                    System.out.printf("x");
                }
                System.out.printf("%d", factor_primo);
                copia_n /= factor_primo;
                productoria *= factor_primo;
            } else {
                factor_primo = siguiente_primo(factor_primo);
            }
        } while (productoria != n);
    } 

Siguiente primo

El siguiente método 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.

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

Verifica primo

Finalmente, implementaremos el módulo \texttt{es\_primo}. Este módulo retornará \texttt{true} si el número es primo y \texttt{false} 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

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

Descomposición de factores: versión alternativa 1

En la versión anterior del método \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.

    private static void descomponer_factores(int n) {
        int productoria = 1;
        int copia_n = n;
        int factor_primo = 2;
        int cant_factores = 0;
        boolean hay_factores = false;
        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) {
                        System.out.printf("x");
                    } else {
                        hay_factores = true;
                    }
                    if (cant_factores == 1) {
                        System.out.printf("%d", factor_primo);
                    } else {
                        System.out.printf("%d^%d", factor_primo, cant_factores);
                    }
                    cant_factores = 0;
                }
                factor_primo = siguiente_primo(factor_primo);
            }
        } while (productoria != n);
        if (hay_factores) {
            System.out.printf("x");
        }
        if (cant_factores == 1) {
            System.out.printf("%d", factor_primo);
        } else {
            System.out.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 un módulo aparte.

Contando factores

La versión del método \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 al método \texttt{escribe\_factor}.

public class Descomposicion_factores_primos_v2_2 {

    static int cant_factores = 0;
    static boolean hay_factores = false;

    private static 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) {
                copia_n /= factor_primo;
                productoria *= factor_primo;
                cant_factores++;
            } else {
                if (cant_factores > 0) {
                    escribe_factor(factor_primo);
                }
                factor_primo = siguiente_primo(factor_primo);
            }
        } while (productoria != n);
        escribe_factor(factor_primo);
    }
} 

Escribiendo factores

Este método \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{\^ }). 
private static void escribe_factor(int factor_primo) {
        if (hay_factores) {
            System.out.printf("x");
        } else {
            hay_factores = true;
        }
        if (cant_factores == 1) {
            System.out.printf("%d", factor_primo);
        } else {
            System.out.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 Java. 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 en Java, el mejor libro que hay es Effective Java de Joshua Bloch. Uno de los libros favoritos de los que se inician en Java es Java: Learn Java in One Day and Learn It Well de  Jamie Chan.

Deja una respuesta

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