Project Euler ->Problema 7

Listando los 6 primeros números primos tenemos al: 2, 3, 5, 7, 11, y 13. Vemos que el 13 es el sexto número primo.
Cuál es el 10.001º número primo?

Es una locura! xD Bue, me demoré su poco pero ta listo😉
Busqué en varias partes cómo saber si un número es primo, y lo que más me convenció es esto:

Un número es primo si no es divisible por otro primo menor a él.

Y como en el ejercicio nos dan los 6 primeros, tenemos la mitad lista. El código, después del salto :B Entonces el código es ésto:

public class Problema7 {
    public Problema7(){
        ArrayList<Long> primos = new ArrayList<Long>();
        primos.add(2l); primos.add(3l);primos.add(5l); primos.add(7l);
        primos.add(11l); primos.add(13l);
        while(primos.size()!= 10001){
            Long numero = primos.get(primos.size()-1)+1;
            Boolean esPrimo=false;
            Boolean salidaOk;
            while(!esPrimo){
                 salidaOk= true;
//                System.out.print("Numero a evaluar: "+numero);
                for(Long val: primos){
//                    System.out.print(" -> "+numero + "/"+val);
                    if (numero % val == 0) {
                        //ya no es un primo, se aumenta el numero en 1
//                        System.out.println(" No es primo. Sale del For:Each");
                        salidaOk=false;
                        break;
                    }
                }
                if (!salidaOk) {
                    //salio del For:Each a la fuerza. Aumenta número en 1
                    numero++;
                }else{
//                    System.out.println(" Número primo encontrado: "+numero);
                    esPrimo=true;
                }
            }
            primos.add(numero);
        }
        System.out.println("Número primo Nº"+primos.size()+" es el: "+primos.get(primos.size()-1));
    }
}

Ahora vamos con la explicación:

  1. Creamos un arreglo para guardar los primos que encontremos. Primero iba a hacerlo con un vector, pero no me funcionaba… así que lo hice con un arreglo, dejándolo como un Long.
  2. Como ya tenemos los 6 primeros, los agregamos.
  3. En un ciclo while, hacemos todo el leseo. El corte es 10001, que lo tomamos como el largo del array (que en estos momentos es 6).
  4. Definimos el número con el que vamos a comparar: Tomamos el último número en array, y le agregamos 1 (osea tenemos 14).
  5. Definimos 2 variables Booleanas para controlar el camino. Una para ver si encontramos un primo, y la otra para ver si aumentamos o no el número.
  6. Seguimos con el segundo while, el cual se va a ejecutar hasta que encontremos un primo. Cuando lo haga, el ciclo termina y guardamos en el arreglo el primo encontrado y volvemos con el primer while.
  7. En el 2º while, definimos la variable de control salidaOk en true.
    Ahora iniciamos otro ciclo, pero ésta vez es un For:Each y lo vamos a ejecutar tantas veces como primos tengamos guardados en el arreglo (la primera vez, entonces se ejecuta 6 veces).
  8. En el For:Each, comprobamos (en la primera vez) que el numero (14) sea divisible por 2. Si es divisible, el número deja de ser un primo, por lo que quebramos el ciclo para no tener que revisar con los primos restantes. Antes de quebrarlo, cambiamos la variable “salidaOk” a false.
  9. Al terminar el ciclo For:Each, vemos el estado de la variable “salidaOk” Si es verdad, quiere decir que encontramos un primo porque terminamos el ciclo correctamente, y cambiamos la variable esPrimo a true. Si no fuera así, aumentamos el número en 1 (osea en este caso queda como 15).
  10. Volvemos al ciclo 2, y esta vez la condición no se cumple, salimos de él y agregamos el número al arreglo.

Y eso sería😉 Si quieren ver cómo se mueve todo adentro, descomenten las líneas de los System.out siempre ayudan para ver por donde va la cosa🙂

El problema número 8 es una locura😯 … así que tengo para rato xD

Adiosin🙂

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, Uncategorized. Guarda el enlace permanente.

4 respuestas a Project Euler ->Problema 7

  1. ignorante dijo:

    Incrementar de a 1, es innecesario. Ya que si tomas cualquier número primo que no sea el 2, será impar y al sumarle 1, es par, por lo que no es primo.

    También tendrías que considerar que si un número no es divisible por ningún número menor a su raíz cuadrada, entonces es primo. Eso te evita preguntar si 17 es divisible por 13 o por 11, cuando claramente no puede serlo.

    • MaritoCares dijo:

      Cachis man lo de los números pares no se me pasó por la mente x_X

      Lo de la raíz… estoy procesando aún xD

      El cosiaco que hice se demoró 10 segundos en encontrar el resultado, considerando tus consejos lo hago de nuevo y supongo debería bajar el tiempo😉

      Gracias y saludos🙂

  2. r4ito dijo:

    Muy interesante esta solución. Después de entender el código (que me tomo un poco xDD) me picaron las manos por probar algunas modificaciones xDD Instale el jdk-devel y termine con esto:

    import java.util.ArrayList;
    public class Problema7 {
      public static void main(String args[]){
        ArrayList primos = new ArrayList();
        Long numero = 1l; Boolean esPrimo;
        while(primos.size()!= 10001){
          numero++; esPrimo=true;
          for(Long val: primos){
            if(numero % val == 0){
              esPrimo=false;
              break;
            }
          }
          if(esPrimo) primos.add(numero);
        }
        System.out.println(primos.get(primos.size()-1));
      }
    }

    No se porque me tiraba unos errores que no existía el método main, así que tuve que modificar eso, y también importar la utilidad de las listas xD ahí me anduve perdiendo pero el código funciona!! ajaja

    Vas a paso firme con los ejercicios eh? Si sigues asi seras level 1 muy pronto xD Saludos.

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