El Proyecto Euler: Problema 3

6/10/2008

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.

«Anterior | Siguiente»

Hay 10 comentarios:

6/10/2008Bucio dice:

:) muy bueno gracias
6/10/2008ZICCO dice:

Hace tiempo yo hice algo similar, pero el reto era obtener todos los números primos de un número entero de 8 dígitos (cifra máxima 99,999,999). Lo intenté hace unos años cuando conseguí un software que me ayudaría con automatización y control… pero mi respuesta tomaba demasiado tiempo, más de 30 minutos. Supe que una persona de EU consiguió todas las respuestas correctas en 30 o 300 milisegundos…
Jamás supe como hacer eso.
7/10/2008hugo_dc dice:

No había podido resolver este problema =/

Tu solución parece bastante sencilla.

Salu2.
7/10/2008Rodrigo Gallardo dice:

Primera optimización sencilla: Dado un número n y un divisor d (es decir, n/d es entero) siempre es cierto que d < sqrt(n) ó n/d < sqrt(n) (Piensalo un poco). Por lo tanto, el bucle no necesita llegar hasta n, basta con que llegue a sqrt(n), lo cual en tu caso, con un número del orden de 10^11, lo reduce al orden de 10^5.
8/10/2008pablasso dice:

Rodrigo, este código no sigue un bucle hasta 10^11, sino solo hasta un 10^3 debido a que num va disminuyendo, tomando el valor del resultado de las divisiones con los factores primos anteriores .
5/11/2008Alejandro dice:

No entiendo por qué dividís num por todos los números impares.
6/02/2009El Proyecto Euler | Pablasso dice:

[...] Problema 3 – Encuentra el factor primo mas grande de un número compuesto. «Anterior | Siguiente» Temas SimilaresEl Proyecto Euler: Problema 1 [...]
11/05/2009ANDRES RODRIGUEZ RODELO dice:

ESTE ES UN NUMERO PRIMO
12457
6 POR (*) 2 -1
21/10/2009Camilo dice:

Corrígeme si me equivoco, pero ¿este bucle no te revisará todos los números impares? Si mi razonamiento me ha llevado por el camino correcto, ese código que tienes te devolverá únicamente el divisor más grande que sea impar, pero no necesariamente que sea un número primo.

Por ejemplo, para num = 480:
El primer divisor impar es 3.
num = 480/3 = 160.
El siguiente divisor es 5.
160/5 = 32.
Despues del 5, no hay ningun numero impar que divida al 32. Por tanto,
el código continúa hasta que termina de revisar todos los números menores al actual num (o sea 32) y al acabar, te presenta “El resultado es 32.”.

¿Es cierto o no es cierto?
24/12/2009GINGER dice:

queeeeeeeeeeeeeeeeeeeeee…………………pedo con ustedes la mancharon bien feo ..no pueden escribir algo mejor osea…………haganse entender……………………….

Escribe tu comentario:

Los mas frikis pueden suscribirse a los comentarios por RSS.