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

Problema 3

Los factores primos de 13195 son 5, 7, 13 y 29.

¿Cual es el factor primo mas grande del número 600851475143?

Los factores primos de un entero positivo, son los números primos que dividen a ese entero exactamente, es decir, sin dejar residuos. Este problema es comúnmente utilizado para criptografía, ya que con los métodos matemáticos y poder de computo que tenemos actualmente no es posible desencriptar llaves grandes en un tiempo razonablemente practico (decenas de años, miles de años, etc).

Una forma de resolver este problema es con un bucle que se vaya dividiendo el número deseado “x” entre números primos, cuando tiene un resultado sin residuo entonces “x” toma ese valor.

Conforme avanzamos ciclos “x” se va reduciendo y nuestro bucle lo va alcanzando. Cuando se alcanzan, eso indica nuestro factor primo mas grande.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <stdio.h>
 
main()
{
    long long i, num = 600851475143LL;
 
    for (i = 3; i != num; i += 2)
    {
        if (num % i == 0) {
            num = num / i;
        }
    }
 
    printf ("El resultado es %d", num);
    return 0;
}

Si bien esto hace mas de tres mil entradas al bucle, es suficientemente eficiente para terminar en 1 milisegundo, lo que me parece razonable si estamos hablando de calcular para un número del orden 10^11 (cientos de miles de millones).

$ time ./003
El resultado es 6857
real 0m0.001s
user 0m0.000s
sys 0m0.000s

Hay muchos métodos de factorización modernos que son una gran mejora a los viejos métodos de factorización de Fermat y son bastante buenos en números de orden de magnitud mayores al que vimos, como el algoritmo rho de Pollard, Quadratic sieve o General number field sieve. (Lo primero que intente fue utilizar el rho de Pollard, pero me estaba costando un hue mucho tiempo hacerlo en C).

Así que si tienes que trabajar sobre números enormes, te vendría bien utilizar uno de estos algoritmos.

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

Problema 2

Cada nuevo termino en la secuencia de Fibonacci es generada agregando los dos términos previos. Comenzando con 1 y 2, los primeros 10 términos serán:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Encuentra la suma de todos los términos pares en una secuencia que no sobrepase los 4 millones.

Para resolverlo de la forma bruta, hay que construir la secuencia de Fibonnaci solamente agregando una condición donde vamos agregando una sumatoria de los números pares, esa verificación es donde muy probablemente se pueda optimizar esto. Mañana salgo de viaje, hasta fines de la siguiente semana revisare que se pudo hacer.

Por cierto, hubiera jurado que el problema antes estaba escrito con el límite de 1 millón, así tenía guardada la solución, me pregunto ¿porque lo habrán cambiado? por lo pronto el siguiente que haga sera completamente nuevo, los dos primeros ya los había resuelto cuando me registre a la página.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include <stdio.h>
 
main()
{
    int sum = 0, a = 1, b = 1, c = 0;
    while ( c < 4000000 )
    {
        c = a + b;
        a = b;
        b = c;
 
        if ( c % 2 == 0 ) {
            sum += c;
        }
    }
 
    printf("resultado: %d\n", sum);
    return 0;
}

Conclusión

Lo mas costoso de esta solución es la comprobación de que los números sean pares, y revisando otras soluciones hay muchas formas de evitar esta comprobación.

Como bien notaron Michoacano y Xiam, resulta que si revisamos la secuencia, podemos notar que cada tercer número es par y ya sabiéndolo de antemano nos podemos evitar la comprobación y sumar solo cada tercer número.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <stdio.h>
 
main()
{
    int sum = 0, a = 1, b = 1, c = a + b;
    while ( c < 4000000 )
    {
        sum += c;
        a = b + c;
        b = c + a;
        c = a + b;
    }
 
    printf("resultado: %d\n", sum);
    return 0;
}

Nuevamente, esto ayudara realmente en rangos mucho mas grandes que el que tenemos.

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

Problema 1

Si listamos todos los números naturales debajo de 10 que son múltiplos de 3 o 5, tenemos 3, 5, 6 y 9. La suma de estos múltiplos es 23.

Encuentra la suma de todos los múltiplos de 3 o 5 debajo de 1000.

Este problema lo he visto como de los ‘recomendados’ para poner en las entrevistas para trabajo, simple y rápido, te dice claramente las 3 condiciones a evaluar.

El operador % regresa el residuo de una división, por lo que podemos iterar de uno en uno hasta el límite superior (1000) y verificar si cada número es perfectamente divisible (el residuo es 0) entre 3 o 5, entonces lo podemos almacenar.

Resuelto en C.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <stdio.h>
 
main()
{
    int sum = 0, i;
    for ( i = 1; i < 1000; i++ )
    {
        if ( (i % 3 == 0) || (i % 5 == 0) ) {
            sum += i;
        }
    }
 
    printf("El resultado es: %d", sum);
}

Conclusión

Comparando con resultados del Proyecto Euler, si bien la solución de fuerza bruta que hice no esta mal, si la pregunta exigiera un limite con cantidades grandes no es eficiente hacer un loop comparando resultado por resultado, sino que es mejor calcular las operaciones por separado.

La suma de números divisibles por 3, la suma de números divisibles por 5 y restando finalmente los números divisibles por 15 que sino tendríamos los divisibles comunes de 3 y 5 contados 2 veces. Se puede evadir por completo cualquier loop si utilizamos progresiones aritméticas.

Para poner un poco en contraste, haciendo benchmark (utilizando gprof) de mi solución para el limite de 1 billón (si si, un uno seguido de 9 ceros), este laptop tarda 15.68 segundos.

En cambio la siguiente versión (versión de sandippal en el foro) que utiliza este principio, tarda menos de .01 segundo, ¿bastante no?.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <stdio.h>
#define NUM 999999999
 
main()
{
  unsigned long long mult3  = NUM / 3;
  unsigned long long mult5  = NUM / 5;
  unsigned long long mult15 = NUM / 15;
  unsigned long long sum3, sum5, sum15;
 
  sum3 = 3  * mult3  * (mult3 + 1) / 2;
  sum5 = 5  * mult5  * (mult5 + 1) / 2;
  sum15 = 15 * mult15 * (mult15 + 1) / 2;
 
  printf("resultado: %lld\n", sum3 + sum5 - sum15);
}

Gracias en especial al comentario de Xiam, grande su explicación.

¿Que es el Proyecto Euler?

El Proyecto Euler es una serie de retadores problemas de matemática/programación que requerirán mas que un poco de conocimientos de matemáticas para resolver. Aunque las matemáticas te ayudarán a tener métodos elegantes y eficientes, el uso de la computadora y habilidades de programación son requeridos para resolver la mayoría de los problemas.

Desde hace tiempo he querido avanzar con ellos y mi desidia no me ha dejado, así que ahora publicaré los problemas que vaya resolviendo (si, uno por uno) y de paso me doy motivación extra.

También es una perfecta oportunidad para que la vasta fauna del internet pueda corregir mi imperfecta manera de programar, así que cualquier corrección no duden en hacerla, mientras mas me equivoco mas aprendo.

Algunas cosas que notar:

• Siempre agradeceré que revisen el problema y den su opinión, planeo equivocarme bastante. Los problemas se encuentran si buscamos en el internets o en la página del proyecto, pero el punto es pensar un poco y hacerlo uno mismo, lo demás es perder el tiempo.
• No pienso leer las respuestas que vienen en el Proyecto Euler hasta que no haya pasado un tiempo considerable desde que lo resolví, entonces publicare la conclusión.
• Siempre buscare que el programa sea mas eficiente, y por eficiente se entiende que el algoritmo ejecute en menos ciclos de maquina, por lo tanto en menos tiempo. No me importa desarrollar superhabilidades para escribirlo en el menor número de lineas ininteligibles posible.
• Los quiero hacer todos en C para aprender, así tarde tres veces más y cometa muchos errores como n00b que soy, no me importa, desde la carrera técnica no lo utilizo y ya dan ganas :-)
• Si planeas hacerlos por tu cuenta, no leas esto antes! básicamente es un spoiler.

Listado de problemas:

• Problema 1 - Suma todos los números naturales menores a 1000 que son múltiplos de 3 o 5.
• Problema 2 - Encuentra la suma de todos los números pares en una secuencia de Fibonacci que no pase los 4 millones.
• Problema 3 - Encuentra el factor primo mas grande de un número compuesto.