Project Euler -> Problema 10

Finalmente😀

Ok resulta que a principios de enero me llamaron de una empresa, y ps resulta que estoy trabajando en vacaciones😀 si😉 Por lo que he tenido bien pocaso tiempo la verdad…

En los tiempos muertos que tengo, ps decidí seguir con los problemas del proyecto😛 así que aquí va el Nº 10.

La suma de los números primos por debajo de 10 es: 2 + 3 + 5 + 7 = 17.
Encuentra la suma de todos los primos por debajo de 2 millones.

Como pueden ver, se parece al problema 7 (vamos… es igual😯 ). Así que dije: ok… cambio el valor por 2e6 y listo… ERROR!! Java estuvo corriendo por MEDIA HORA (si… esperé todo el rato xD) hasta que finalmente cancelé el proceso. Mi máquina es relativamente rápida… por lo que esperar hasta que terminara NO era una opción (recuerden que las respuestas tienen que correr en un máquina antigua, y en menos de 1 minuto).

En los comentarios del problema 7, Mr. Ignorante me dio el corte necesario para optimizar el código.  Por lo que manos al teclado, logré llegar a la respuesta😛

El código es el siguiente:

public class Problema10 {
    public Problema10(){
        ArrayList<Long> primos = new ArrayList<Long>();
        Double raizNumero; Long suma;
        primos.add(2l); primos.add(3l);/*primos.add(5l); primos.add(7l);
        primos.add(11l); primos.add(13l);*/
        //aca con trampa... porque uno sabe cual es la suma de los de arriba
//        suma = 41l;
        suma=5l;
        while (primos.get(primos.size()-1) <= 2e6){
            Long numero = primos.get(primos.size()-1)+2;
            Boolean esPrimo=false;
            Boolean salidaOk;
            while(!esPrimo){
                 salidaOk= true;
//                 System.out.println("Numero a evaluar: "+numero+" {");
                 raizNumero = Math.floor(Math.sqrt(numero));
//                 System.out.print("\tPrimer Corte Control: "+raizNumero+"\n\t ");
                for(Long val: primos){
//                    System.out.print("->"+numero + "/"+val+"  ");
                    if (val>raizNumero) {
//                        System.out.print("\n\tEl divisor es mayor a la raíz. No es necesario seguir.");
                        break;
                    }else{
                        if (numero % val == 0) {
                        //ya no es un primo, se aumenta el numero en 2
//                        System.out.print("\n\tNo es primo. Sale del For:Each\n}\n");
                        salidaOk=false;
                        break;
                        }
                    }
                }
                if (!salidaOk) {
//                    salio del For:Each a la fuerza. Aumenta número en 2
                    numero+=2;
                }else{
//                    System.out.print("\n\tNúmero primo encontrado: "+numero+"\n}\n");
                    esPrimo=true;
                }
            }
            primos.add(numero);
            if (numero<2e6) {
                suma+=numero;
            }
        }
        System.out.println("Suma de los números primos menores a "+2e6+" es: "+suma);
    }
}

😀

Eso si, tiene un problema… si se fijan, el while termina con el primo inmediatamente después del número deseado. En éste caso, termina en el 2.000.003, por lo que en teoría no sirve. El arreglo que le hice, fue preguntar nuevamente si era menor o no. Y de ésta forma quedo correcto😀

GENERACIÓN CORRECTA (total time: 4 seconds)

En el PC del trabajo… viejo y lento, osea que la respuesta es aceptable🙂

Acerca de MaritoCares

Ingeniero Informático. Con tendencias a la programación en [C#, VB].NET, Java(Web principalmente...), PHP, JavaScript, algo mínimo de [ruby, python], y el clásico C.
Esta entrada fue publicada en Java, Problemas Project Euler. Guarda el enlace permanente.

10 respuestas a Project Euler -> Problema 10

  1. ignorante dijo:

    En mi PC tu solución me tarda 1.367 milisegundos.
    Tiene varios problemas, entre ellos la claridad del código, pero también la eficiencia. Usas Long y Boolean en lugar de los tipos primitivos (long y boolean).
    Una versión mejorada tarda 528 milisegundos.

    private static final long LIMIT = 2000000;
    private static long sum(List values) {
    long res = 0l;
    for (int i = 0; i < values.size(); i++) {
    res += values.get(i);
    }
    return res;
    }

    private static boolean esPrimo(int x, List primos){
    int i = 1;
    int factor;
    final int size = primos.size();
    boolean prime = true;
    while(prime && i x){
    i = size;
    }else{
    prime = x % factor != 0;
    }
    i++;
    }
    return prime;
    }

    private static void mejorado() {
    List primos = new ArrayList(10000);
    primos.add(2);
    int current = 3;
    while(current <= LIMIT){
    if(esPrimo(current, primos)){
    primos.add(current);
    }
    current +=2;
    }
    sum(primos);
    }

  2. ignorante dijo:

    La última línea debería ser:

    System.out.println(“Suma de los números primos menores a ” + LIMIT + ” es: ” + sum(primos));

  3. D4rk dijo:

    En problemas en los que se quiera hayar la lista de los numeros primos menores que un numero N(en este caso N=2*10^6), existe un algoritmo eficiente, que tal vez te recuerdes del cole Criba de Eratóstenes:
    Aqui la implementacion del algoritmo:(Esta en c++, espero se entienda XD)
    #include
    #include
    #define N 2000000
    bool prime[N+1];
    long long Criba(){
    std::fill(prime,prime+N,true);//relleno todos los valores con true
    prime[0]=prime[1]=false;// 0 y 1 no son primos😄
    long long ans=0;
    for(long long i=2;i<N;i++){
    if(prime[i]){
    ans+=i;//para sumar el numero primo a nuestro resultado
    //utilizo el long long para que no haya overflow con el int en el caso de numero del orden de 10^5
    //(10^5)* (10^5) se pasa de 2^31😄
    for(long long j=i*i;j<N;j+=i)prime[j]=false;//tacho todos los multiplos de ese numero porque ya No son primos
    }
    }
    return ans;
    }
    int main(){
    printf("%lld\n",Criba());
    }

    • D4rk dijo:

      Bueno aqui la explicacion(por si No se entiende el algoritmo):
      1.Comienzas con una tabla de los numeros de 2 hasta N (0 y 1 No se consideran primos XD)
      2. Ves si el numero es primo(osea ves sino esta marcado).
      3. Si es primo(no esta marcado)marcas a todos sus múltiplos(ya que ya No serian primos).
      Y para este problema lo sumas( porque quieres la suma de todos los primos XD).

      Espero te sirva para proximos problemas🙂 …

  4. Ivan Mrsnik dijo:

    Yo he creado una modificacion de la criba de erastotenes que es varios millones de veces mas rapida que esta, hace parecer a cualguier lenguaje en un lenguaje C, 1000 millones en segundos, en una laptop viejita, pero tengo un problema, como calculo los numeros extremadamente grandes, muchos de ellos rellenan con 0 los numeros y adicionalmente el espacio en disco, si guardo en una base de datos los discos de Terabyte se vuelven pequeños. Un numero de un millon de digitos es un mega. Mil de ellos un gigabye. Un millon un terabyte,la alternativa si almacenara como ascii ya que ub byte es 256, o se pdria almacenar mas o como bit, pero dificultaria mucho los calculos y hacerlo mas lento.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s