Recursividad - Ejercicios resueltos 10

Otro algoritmo interesante es el que descompone un número cualquiera en sus factores primos. Lo más entretenido de este ejercicio es que nos prepara para para  recorrer datos en una estructura de árbol (como en el ejercicio de a elevado a n).

3.- Confeccione una función recursiva que permita determinar o presentar los factores primos de un número n.
Ejemplo: 90 = 9 * 10 = (3 * 3) * (2 * 5).

Encontrar los factores "medios" de un número (por así decirlo) pasa por encontrar el factor más cercano a la raíz cuadrada del número. Tomando sólo la parte entera de la raíz cuadrada de n se puede obtener el factor exacto o un número un poco menor. Si es menor lo incrementamos hasta encontrar el factor buscado. El otro factor se obtiene dividiendo n por el factor encontrado. Si los factores no son primos se recurre con estos valores. Por lo tanto la condición de paro (borde) es que n se haya transformado en primo.

La implementación en Java es la siguiente:

public static void factoresPrimos(int n) {

 //Si n es primo se imprime.
 if (esPrimo(n)){
  System.out.print("*"+n+" ");
  return;
 }

 //Si n no es primo calculamos el primer factor... 
 int factor1 = (int) Math.sqrt(n);
 
 while (n % factor1 !=0) factor1++;
 
 //... recurrimos por el primer factor
 factoresPrimos(factor1);

 //... y luego recurrimos por el siguiente factor.
 factoresPrimos(n/factor1);
}