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.zipSi alguien se anima a intentar hacer lo mismo más rápido, adelante.
Saludos
He hecho una modificación y ya tarda sólo 13 segundos.
Aquí el binario:
http://www.gratisweb.com/stratdes/NumerosP...sPrimosv0.2.zipSaludos
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!
Hola,
que metodo has utilizdo? Fuerza bruta u otro sistema? Un saludo!
Vicente
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:
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
CitarLoover, lo interesante del caso es ver cuanto tarda en hacer las miles de operaciones que se necesitan.
Tan solo era una broma ;)
Cita de: "Loover"CitarLoover, 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.
CitarQUOTE (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!
Cita de: "StraT"CitarQUOTE (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.
Como dato añadir que tarda aprox. 2 minutos en calcular y mostrar los primos del 1 al 10 millones
Saludines
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
¿Con caché o sin caché? ;)
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
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.
CitarAnda 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
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
Si fuera par se podría dividir entre dos y ya no sería primo xD
Saludos
Ya ya, por eso lo digo, que en el codigo que has puesto compruebas pares e impares
No... resulta que el 2 es el primer número que se comprueba, y si da exacto rompe el bucle.
Saludos
¿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
Cita de: "Loover"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!
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.aspProbé 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.
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?
Cita de: "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?
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.
Mirad tambien Miller-Rabin si queréis generar números primos muy grandes. Un saludo!
Vicente
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:
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
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 [] ;)
Citarademá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