jueves, 15 de abril de 2010

Calculando números primos (C++)

Este programa calcula todos los números primos hasta el 4294967295, o 232, que es el numero de 32 bits mas grande.
También mide el tiempo que tarda en calcularlos, que suelen ser unas cuantas horas, aunque depende de tu computadora.
Los tiempos en un ordenador a 3.4 GHz serán mas o menos:
Numeros total hh:mm:ss Numeros primos
100000 00:00:00 9593
1000000 00:00:00,3 78499
10000000 00:00:03,7 664580
100000000 0:01:20 5761456
1000000000 0:32:18 50847535
4294967295 sobre 5 horas? Todavia no lo calculé

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

#define MAX_INT 4294967295

int main()
{
    unsigned int *primos = new int [220000000];
    primos[0] = 2;
    primos[1] = 3;
    unsigned int n = 2;  // Nºde primos guardados en la matriz
    unsigned int i = 3;  // Para recorrer desde 3 a MAX_INT 
    unsigned int j, d;   // d = sqrt(i)
    clock_t tA, tB;

    tA = clock();
    while (i<MAX_INT)
    {
        d = unsigned int(sqrt(i+=2));
        for (j=1; d>=primos[j] && i%primos[j]!=0; j++) ;
        if(d<primos[j]) primos[n++] = i;
    }
    tB = clock();

    double t = double(tB-tA)/(double)CLOCKS_PER_SEC;

    printf("\nEncontrados %u numeros primos en %.3f segundos\n.",n,t);
    
    // para mostrar todos los numeros
    // for(i=0;i<p;i++) printf("%u\n",primos[i]);
    
    system("PAUSE");
    return 0;
};

Comparte o puntua esta publicación ▼

2 comentarios:

ivan dijo...

Se ve bien para empezar a sacarlos pero en menos de 20 dias, he sacado el mejor código que evalue los primos y lo que me detiene es el uso grande de memoria en procesador de 2 gigahertz logro sacar de 1 hasta 1900 millones en 39 seg todos los primos que hay,asi que si llegara a sacar hasta los 32 bits llegaraia a 2 minutos apenas

DavidXL dijo...

¿Dices que as conseguido hacer un programa que calcula todos los numero primos hasta 4294967295 en tan solo 2 minutos con un procesador a 2gh? me resulta increíble!!, por otro lado el tiempo que tarda en calculas si un numero es primo cada vez es mayor, a medida que el numero aumenta (fijate en la tabla, el tiempo que tarda crece exponencialmente) por lo menos en mi programa.

¿Podrias decirme como lo hiciste, que algoritmo usas, ...?
Gracias

Publicar un comentario