Calcular Números Primos Del 1 Al 1.000.000

[zupervaca]

 Lo unico que puede añadir es que no conozco un numero primo par, si no contamos el 2 claro esta, aunque tampoco me he puesto a calcular nunca los infinitos numeros primos existentes :P

[StraT]

 Si fuera par se podría dividir entre dos y ya no sería primo xD

Saludos

[zupervaca]

 Ya ya, por eso lo digo, que en el codigo que has puesto compruebas pares e impares

[StraT]

 No... resulta que el 2 es el primer número que se comprueba, y si da exacto rompe el bucle.

Saludos

[zupervaca]

 ¿y por el 2 que es el unico numero primo par no optimizas? ummm, yo directamente lo mostraria como primo sin ningun tipo de comprobacion y despues en el bucle principal pondria un +=2

[dracks]

Aunque creo que es más probable que los de SETI encuentren antes a ET.

Pos yo creo que esto no es problema, solo tienen que ir al almacen de los estudios de quienes hicieron la peli :P o a alguna tienda de recuerdos de holligod :P o como se llame...


Pos... piensa que possibles numeros de que sean primos con 10 millones de digitos, en realidad son inferiores a la mitad de los numeros contenidos dentro de este rango de numeros :P



Suerte!

[Velario]

 Yo hace tiempo estuve curioseando con C# también en el tema de calcular números primos.
Todas las implementaciones que hacia me parecían demasiado lentas así que me puse a buscar
información sobre el tema y dí con un enlace muy interesante :

http://www.codeproject.com/csharp/highspee...rimenumbers.asp

Probé esa implementación con el BitArray y quede pasmado por la diferencia de velocidad en el
calculo respecto a mis implementaciones.

Los datos hablan por si mismos. :

664580 números primos encontrados en 10000000
La búsqueda de primos ha tardado 3 segundos

5761456 números primos encontrados en 100000000
La búsqueda de primos ha tardado 43 segundos

Claro está estas cifras son haciendo solo el calculo, si al código le añadimos un WriteLine para que
vaya mostrando los primos encontrados por pantalla, el tiempo aumenta estando sujeto a lo que
tarde en mostrar los números por el terminal.

Algunos datos mas de interés:

Procesador : Athlon64 3200+
Memoria : 2G de RAM
Sistema : Linux
Mono JIT compiler version 1.1.10 (Sin ninguna optimización añadida)

Saludos.

[Marci]

 Velario, puedes poner lo que tarda el código original de StraT en tu máquina para ver que mejora se consigue con la Criba de Eratosthenes en el  mismo ordenador?

[Velario]

 

Velario, puedes poner lo que tarda el código original de StraT en tu máquina para ver que mejora se consigue con la Criba de Eratosthenes en el  mismo ordenador?

Por supuesto.

Tiempos con el codigo original de StraT :
------------------------------------------------------------------------
Hay 78499 números primos del 0 al 1000000
La búsqueda de primos ha tardado 00:00:02.4659440 segundos

Hay 664580 números primos del 0 al 10000000
La búsqueda de primos ha tardado 00:01:02.6601400 segundos

Hay 5761456 números primos del 0 al 100000000
La búsqueda de primos ha tardado 00:28:55.4528680 segundos
------------------------------------------------------------------------

Tiempos con mi codigo :
------------------------------------------------------------------------
78499 numeros primos encontrados en 1000000
La búsqueda de primos ha tardado 00:00:00.3359050 segundos

664580 numeros primos encontrados en 10000000
La búsqueda de primos ha tardado 00:00:03.8081890 segundos

5761456 numeros primos encontrados en 100000000
La búsqueda de primos ha tardado 00:00:42.4601680 segundos
------------------------------------------------------------------------

Los tiempos son lo que tarda solo el calculo, sin mostrar los numeros por pantalla.

Saludos.  

[Vicente]

 Mirad tambien Miller-Rabin si queréis generar números primos muy grandes. Un saludo!

Vicente

[ZüNdFoLGe]

 Otra forma de encarar la solucion de calcular los n primeros numeros primos es usando programacion dinámica, guardando en un vector los numeros primos que se van encontrando, y luego a cada numero dividirlo solo por las soluciones almacenadas en el vector (numeros primos hasta el momento...) para evitar dividirlo entre todos los menores que el, o como acabo de ver en el codigo de StraT que se divide cada numero por los menores hasta el truncamiento de la raiz del numero. Usando la técnica divide&conquer la solucion es la misma porque tomando cada numero nuevo como un subproblema se almacena en el vector los numeros primos menores, los cuales los uso para contar la cantidad total y para dividir al nuevo numero. El codigo seria algo asi:

Código [Seleccionar] Expand


void nPrimos(int N) {

  int [] vector= new int [N];
  int cantPrimos= 1; // considero que N >= 2
  vector[0]= 2;

  for(int i=3; cantPrimos<N; i++){
      int h=0;

      while((h<cantPrimos) && (i % vector[h] ! =0))
         h++;

       if (h==cantPrimos) {
         vector[cantPrimos]=i;
         cantPrimos++;
       }
  }
  cout << cantPrimos;
}



el que tenga tiempo de compararlo en tiempo que lo ponga  (ole) , pero el ahorro en la cantidad de operaciones esta a la vista. Espero que este thread termine de una vez!!!  (asco)

Salu2
     

[zupervaca]

 Lo dicho antes un i+=2 y compruebas la mitad de números, además por lo que veo tu código empieza desde 3 con lo que no tienes que hacer ninguna modificación. Este sistema es el que hablan en la url que han puesto antes. Podrías optimizarlo mas usando aritmética de puntos y así ahórrate el [] ;)

[ZüNdFoLGe]

 

además por lo que veo tu código empieza desde 3 con lo que no tienes que hacer ninguna modificación. Este sistema es el que hablan en la url que han puesto antes.

Lo de ninguna modificación : CIERTO... no tiene sentido apartar el 2.
Lo de el sistema es el que hablan en la url que han puesto antes : FALSO...
ese sistema se basa en la criba de eratóstenes, que se comienza con un vector marcado, de tamaño N (cota superior de los numeros a calcular) y se van eliminando los múltiplos del índice empezando por el 2, es decir desmarcandolos. Por tanto no es el mismo sistema, de hecho en ninguna parte se observa optimización...al contrario...
Lo unico que tienen de parecido es que se usa un vector para almacenar resultados temporales.

Salu2