El Proyecto Euler: Problema 3

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.

#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.