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. 

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

Analizaremos 3 algoritmos para descomponer factores en Python. 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étodo principal

Iniciamos el análisis con el método principal, este método será el mismo para las tres versiones que analizaremos para la descomposición de factores primos. Este método básicamente realiza la lectura de datos, la validación de los datos de entrada y finalmente, la invocación al método \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étodo \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étodo principal y no el método \texttt{descomponer\_factores}.

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

Versión usando divisiones sucesivas

Analizaremos la primera versión del algoritmo para descomponer factores en Java. En esta versión usaremos las divisiones sucesivas como mecanismo para encontar los factores primos. Todo esto se implementará en 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, 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étodo.

Control de iteración

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

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

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

private static 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{true}.

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

private static void descomponer_factores(int n) {
        System.out.printf("%d = ", n);
        int factor_primo = 2;
        boolean primer_factor = true;
        do {
            if (n % factor_primo == 0) {
                if (primer_factor) {
                    System.out.printf("%d", factor_primo);
                    primer_factor = false;
                } else {
                    System.out.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 el método \texttt{siguiente\_primo}.

    private static void descomponer_factores(int n) {
        System.out.printf("%d = ", n);
        int factor_primo = 2;
        boolean primer_factor = true;
        do {
            if (n % factor_primo == 0) {
                if (primer_factor) {
                    System.out.printf("%d", factor_primo);
                    primer_factor = false;
                } else {
                    System.out.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 este método por ello. Asumimos que existe un método llamado \texttt{es\_primo} que se encarga de verificar si un número es primo.

    private static 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 el método \texttt{es\_primo}. Este método 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 Java en donde analizamos seis diferentes versiones que permiten determinar si un número es primo o no.

    private static boolean es_primo(int n) {
        if (n <= 1) {
            return false;
        }
        boolean encontro_divisores = false;
        int i = 2;
        while (i <= sqrt(n) && !encontro_divisores) {
            if (n % i == 0) {
                encontro_divisores = true;
            }
            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 el atributo \texttt{cant\_factores} que indicará cuantos factores iguales existen. Al inicio este atributo lo 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étodo \texttt{escribe\_factor}.

    private static void descomponer_factores(int n) {
        System.out.printf("%d = ", n);
        int factor_primo = 2;
        do {
            if (n % factor_primo == 0) {
                cant_factores++;
                n /= factor_primo;
            } else {
                escribe_factor(factor_primo);
                factor_primo = siguiente_primo(factor_primo);
            }
        } while (n > 1);
        escribe_factor(factor_primo);
    } 

Escribiendo factores

El método \texttt{escribe\_factor} tiene como objetivo escribir el factor en cuestión. Posee 1 parámetro y usa dos atributos:

  •  \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{true} 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{true}, \texttt{factor\_primo} fuera 2 y \texttt{cant\_factores} fuera 3, se imprimiría 2^3.
  • Si \texttt{primer\_factor} fuera \texttt{false}, \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{false}, \texttt{factor\_primo} fuera 2 y \texttt{cant\_factores} fuera 1, se imprimiría \times 2. En este caso no se imprime el exponente. 
    private static void escribe_factor(int factor_primo) {
        if (cant_factores > 0) {
            if (!primer_factor) {
                System.out.printf("x");
            } else {
                primer_factor = false;
            }
            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 *