PROGRAMA CHAR DE FACTORES PRIMOS

Escribir un programa que pida varios números, hasta que el usuario quiera terminar, y los descomponga en factores primos.
No seremos especialmente espléndidos en la optimización, por ejemplo, no es probable que valga la pena probar únicamente con números primos para los divisores, podemos probar con algunos que no lo sean, al menos en este ejercicio no será una gran diferencia.
Piensa un momento en cómo resolverlo e inténtalo, después puedes continuar leyendo.
Lo primero que se nos ocurre, al menos a mi, cuando nos dicen que el programa debe ejecutarse mientras el usuario quiera, es implementar un bucle do..while, la condición de salida será que usuario responda de un modo determinado a cierta pregunta.

En cada iteración del bucle pediremos el número a descomponer y comprobaremos si es divisible entre los números entre 2 y el propio número.

No podemos empezar 1, ya que sabemos que todos los números son divisibles por 1 infinitas veces, por eso empezamos por el 2.

Pero si probamos con todos los números, estaremos intentando dividir por todos los pares entre 2 y el número, y sabremos de antemano que ninguno de ellos es un factor, ya que sólo el 2 es primo y par a la vez, por lo tanto, podemos probar con 2, 3 y a partir de ahí incrementar los factores de dos e dos.
Por otra parte, tampoco necesitamos llegar hasta el factor igual al número, en realidad sólo necesitamos alcanzar la raíz cuadrada del número, ya que ninguno de los números primos entre ese valor y número puede ser un factor de número.

Supongamos que tenemos en número 'n', y que la raíz cuadrada de 'n' es 'r'. Si existe un número 'x' mayor que 'r' que es un factor primo de 'n', por fuerza debe existir un número 'h', menor que 'r', que multiplicado por 'x' sea 'n'. Pero ya hemos probado todos los números por debajo de 'r', de modo que si existe ese número 'h' ya lo hemos extraído como factor de 'n', y si hemos llegado a 'r' sin encontrarlo, es que tampoco existe 'x'.

Por ejemplo, el número 257. Su raíz cuadrada es (aproximada), 16. Es decir, deberíamos probar con 2, 3, 5, 7, 11 y 13 (nuestro programa probará con 2, 3, 5, 7, 9, 11, 13 y 15, pero bueno). Ninguno de esos valores es un factor de 257. El siguiente valor primo a probar sería 17, pero sabemos que el resultado de dividir 257 por 17 es menor que 17, puesto que la raíz cuadrada de 257 es 16.031. Sin embargo ya hemos probado con todos los primos menores de 17, con resultado negativo, así que podemos decir que 17 no es factor de 257, ni tampoco, por la misma razón, ningún número mayor que él.

Ya tenemos dos buenas optimizaciones, veamos cómo queda el programa:


#include <iostream> // biblioteca para uso de cout
using namespace std;

int main()
{
   int numero;
   int factor;
   char resp[12];
 
   do {
      cout << "Introduce un número entero: ";
      cin >> numero;
      factor = 2;
      while(numero >= factor*factor) {
         if(!(numero % factor)) {
            cout << factor << " * ";
            numero = numero / factor;
            continue;
         }
         if(factor == 2) factor++;
         else factor += 2;
      }
      cout << numero << endl;
      cout << "Descomponer otro número?: ";
      cin >> resp;
   } while(resp[0] == 's' || resp[0] == 'S');
   return 0;
}