El Proyecto Euler: Problema 5

El Proyecto Euler es una serie de problemas de programación, si quieres enterarte de que va esto, lee la introducción.

Problema 5

Espero que Michoacano y los señores de Kobol me pueda perdonar, pero seguiré con la regla de «un minuto» para llegar a los problemas retadores en que ya no es posible las soluciones de fuerza bruta. Los siguientes dos son sencillos de resolver sino te pones a tratar de optimizarlos, pero el 7 me llamó la atención porque trata de nuevo de números primos y ese si trataré de optimizarlo. En fin, les paso de rapidito las soluciones cochinas de 5 y 6.

2520 es el número mas pequeño que puede ser dividido por cada uno de los números del 1 al 10 sin dejar residuos.

¿Cuál es el número mas pequeño perfectamente divisible -sin residuos- por todos los números del 1 al 20?

Como nos están pidiendo el mínimo común múltiplo de 20 números, la solución de fuerza bruta es bastante simple. Hacemos un bucle donde probamos número por número entre cada una de las opciones, si nos deja residuo entonces lo descartamos y vamos por el siguiente. Así hasta encontrar el indicado.

#include <stdio.h>
#define LIMIT 20

main()
{
  int flag = 1, n = 1, i;
  
  while ( flag )
  {
    n++;
    
    for ( i = 1; i <= LIMIT; i++ )
    {
      if ( (n % i) != 0 ) {
        break;
      }
      
      flag = i == LIMIT ? 0 : 1;
    }
  }
  
  printf("%d\n", n);
  return 0;
}

Mejoras

Muchísimas.

Leí que se pueden sacar los factores primos de cada unos de los números de 1 al 20 y entonces el producto de ellos nos daría el resultado. Hacer eso sería una solución mucho -pero mucho- mas rápida y mejor que esta.