Calcular Números Primos Del 1 Al 1.000.000

[StraT]

 Mirad, me aburría, que le vamos a hacer, y miré a ver si podía programar una aplicación que calculara primos. Y no contento con ello, me puse a ver cuan rápida podía ser.

La he programado en c# y tarda entre 20 y 22 segundos en calcular los primos que hay entre el 1 y el 1.000.000 (ATHLON 64BITS 3500 1GB RAM).

Si queréis probarla, aquí está (necesita .net framework):

http://www.gratisweb.com/stratdes/NumerosPrimos.zip


Si alguien se anima a intentar hacer lo mismo más rápido, adelante.

Saludos

[StraT]

 He hecho una modificación y ya tarda sólo 13 segundos.

Aquí el binario:


http://www.gratisweb.com/stratdes/NumerosP...sPrimosv0.2.zip



Saludos

[Loover]

 Crea una caché en disco duro, así la siguiente vez que los calculques tardará 0,00x (el que sea tiempo de lectura de disco y representación en pantalla) segundos :P

Esta mierda de post es mi primero del año, yuju!

¡Féliz año!

[Vicente]

 Hola,

que metodo has utilizdo? Fuerza bruta u otro sistema? Un saludo!

Vicente

[StraT]

 Fuerza bruta combinada con algo de matemáticas.

Loover, lo interesante del caso es ver cuanto tarda en hacer las miles de operaciones que se necesitan.

Aquí el código va:

Código [Seleccionar] Expand

using System;
using System.Collections.Generic;
using System.Text;
using System.Timers;

namespace NumerosPrimos
{
   
   class Program
   
   {

       public void SacaNumerosPrimos(int max)

       {

           int nump = 0;
           double x = Math.Sqrt(max);
           x = Math.Round(x);
           int xi = (int)x;

           for (int i = 1; i <= max; i++)
           
           {
               
               bool compuesto = false;

               for (int j = 2; j <= xi; j++)
           
               {

                   if ((i % j) == 0 && i != j)

                   {

                       compuesto = true;
                       break;

                   }

               }

               if (compuesto == false)
               
               {

                   System.Console.WriteLine("El " + i + " es un número primo"); nump++;
               
               }

           }

           System.Console.WriteLine("Hay " + nump + " números primos del 0 al " + max);

       }

   }

   class main

   {

       static void Main(string[] args)
       
       {

           System.DateTime init = System.DateTime.Now;
           Program program = new Program();
           program.SacaNumerosPrimos(10000000);
           System.DateTime end = System.DateTime.Now;
           System.TimeSpan total = end - init;
           System.Console.WriteLine("La búsqueda de primos ha tardado " +
               total.Seconds + " segundos");
           System.Console.ReadLine();

       }

   }

}


Saludos

[Loover]

 

Loover, lo interesante del caso es ver cuanto tarda en hacer las miles de operaciones que se necesitan.

Tan solo era una broma ;)

[ethernet]

Loover, lo interesante del caso es ver cuanto tarda en hacer las miles de operaciones que se necesitan.

Tan solo era una broma ;)

Pues a mi me parece una solución muy eficiente, efectiva e inteligente.  

[StraT]

 

QUOTE (Loover @ 01/01/06, 17:50 )
QUOTE
Loover, lo interesante del caso es ver cuanto tarda en hacer las miles de operaciones que se necesitan.


Tan solo era una broma wink2.gif

Pues a mi me parece una solución muy eficiente, efectiva e inteligente.

Y lo es, si no fuera porque sólo quiero probar la velocidad de cálculo, si sólo quisiera mostrar primos haría una cache o un fichero binario con los números y los leería, pero repito, quiero ver cuan rápido se puede hacer.

Saludos!

[ethernet]

QUOTE (Loover @ 01/01/06, 17:50 )
QUOTE
Loover, lo interesante del caso es ver cuanto tarda en hacer las miles de operaciones que se necesitan.


Tan solo era una broma wink2.gif

Pues a mi me parece una solución muy eficiente, efectiva e inteligente.

Y lo es, si no fuera porque sólo quiero probar la velocidad de cálculo, si sólo quisiera mostrar primos haría una cache o un fichero binario con los números y los leería, pero repito, quiero ver cuan rápido se puede hacer.

Saludos!

Sí, entiendo que es un benchamark, pero me ha impactado la respuesta de loover, porque yo tb soy muy amigo de calcularlo todo XD.

[StraT]

 Como dato añadir que tarda aprox. 2 minutos en calcular y mostrar los primos del 1 al 10 millones

Saludines

[Loover]

 Que pena que vayas con retraso: http://www.vnunet.es/Actualidad/Noticias/I...B3n/20031212020

¿Cuánto tardarías en calcular uno de 10 millones de dígitos? :)

100.000$ de primo WOW

[Mars Attacks]

 ¿Con caché o sin caché? ;)

[StraT]

 Creeis que es posible? para empezar tendría que encontrar un número de 10.000.000 de dígitos para ponerlo como tope y empezar a calcular primos...

Buf

Saludos

[Loover]

 No, no es posible con tu ordenador, a no ser que dispongas de 100 años.

Los de GIMPS se lo montan mejor, con su sistema distribuido de ordenadores. Es algo así como el programa SETI (ese que busca marcianitos en el espacio). Un usuario se descarga el programa, lo deja residente en memoria y este se activa cuando no se utiliza mucho la CPU (por ejemplo cuando salta el salvapantallas). Entonces el programa recibe un paquete de datos, lo calcula y lo devuelve... y luego otro, etc. Y esto muchísimos ordenadores en todo el mundo.

Los de GIMPS no buscan números primos exactamente, buscan números MERSENNE. Un número Mersenne es 2^número_primo - 1. Es decir, 2 elevado a número primo menos 1. Pero claro para esto tienes que calcular todos los números primos e ir verificando.

Están muy cerca de llegar a la cifra de 10 millones del premio, el pasado 15 de diciembre ya estaban por los 9 millones de cifras. Pero vamos, llevan desde 1996 con el proyecto así que va lento el asunto.

Anda que no me gustaría a mi un sistema distribuido como este pero para renderizar, sí, estaría MUY BIEN.

PD: Pero quién sabe, igual tienes una potra increible y el número de 10 millones que eliges al azar es un número primo. Te tiras un mes para verificarlo y ganas el premio :D Aunque creo que es más probable que los de SETI encuentren antes a ET.

[StraT]

 

Anda que no me gustaría a mi un sistema distribuido como este pero para renderizar, sí, estaría MUY BIEN.

Estaría muy bien si no fuera por el tiempo de transferencia de los paquetes a renderizar, xD.

Saludos