Buscando números primos, con la criba de Eratóstenes

[leosansan]

Iniciado por CalgaryCorpus

No me gusta que asignar un valor a una variable, por ejemplo

Código C++:

x = 1
 

tome mas tiempo que preguntar que valor tiene y luego asignarla, por ejemplo

Código C++:

if( x == 0 ) 
   x = 1;
 

Pero el programa mostrado previamente es una muestra que este comportamiento se da, entonces, tomando partido de eso mismo, y otros cambios, se puede bajar aun mas el tiempo de ejecución

- nums en vez de hacerlo un arreglo de enteros, hacerlo un arreglo de bool
- Preguntar si ya se tiene el valor true, y solo asignárselo cuando no lo sea

Entonces la nueva versión queda así:
...................................
Y esta version deberia tomar menos tiempo que todas las anteriores... creo
Al menos en mis pruebas, asi es

Creo que has llevado mi idea de no tachar más de una vez al éxito total. Lo has bordado con el uso de bool en lugar de int.

Y tanto que toma menos tiempo. Para el caso de 10^8 lo baja en casi 1 segundo.

Ya hemos exprimido al máximo la Criba de Erastótenes.... ¿o tal vez no?.

A bote pronto veo un desperdicio de memoria en los arrays usados:

* nums está dimensionado a N y, como sólo usamos los impares, podríamos bajarlo a N/2.

* prims está dimensionado a N y los primos son sólo una fracción de los impares hasta N.

Con estas dos ideas básicas puede aumentar el límite de primos, antes de que cruja el programa, de 10^8 a 2.745 x 10^9, lo que no está nada mal:

Código C++:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#define N 100000000 /** 2745000000: hasta aqui mi PC calcula los primos **/
#define N_medio N/2  /**........ por ahora...y con este metodo.......... **/
 
int main(){
  unsigned int  i, j , z , x = 0 , N_PRIMS , rq ;
  unsigned int potencias[]={100,1000,10000,100000,1000000,10000000,100000000,1000000000};
  unsigned int Relacion, relacion[]={4,5,8,10,12,15,17,19};
  rq = (int) ( sqrt( N ) );
/** por ejemplo sqrt(1.600.000.000) = 40.000 ==> solo llegamos a 39.999 **/
  if ( rq % 2 == 0 )
    rq--;
  for ( i = 0 ; i < 8 ; i++ )
    if ( N / potencias[i] >= 1 && N / potencias[i] < 10 ){
      Relacion = relacion[i];
      break;
    }
  N_PRIMS = ( N / Relacion );
  bool *nums  = calloc( N_medio , sizeof ( bool ) );
  if( !nums ){
    printf("nums::No hay espacio suficiente en memoria");
    return EXIT_FAILURE;
  }
  unsigned int *prims = calloc( N_PRIMS , sizeof ( unsigned int ) );
  if( !prims ){
    printf("prims::No hay espacio suficiente en memoria");
    return EXIT_FAILURE;
  }
  prims[x] = 2;
  for( i = 3  , z = 1 ; i <= N ; i += 2 , z++ ){
    if( nums[z] )
      continue;
    prims[++x] = i ;
    if( i > rq )
      continue;
    for( j = z + z * i ; j <= N_medio ; j += i ){
      if( !nums[j] )
        nums[j] = true;
    }
  }
  printf( "\n\tHasta %u hay %u numeros primos\n" , N , x + 1 );
  printf( "\n\t\tEl ultimo es: %u \n" , prims[x] );
 
        /***** PARA IMPRIMIR POR GRUPOS *****/
 
/** quita el "+" que aparece al final de la siguiente linea  **/
 
/************************************************************+/
  system ( "pause" );
  char cifra[10] , cad1 [] = "%" , cad2 [] = "u" ;
  unsigned int k = 1 , n1 = N , lineas = 0;
  for(  ;  n1 ; k ++, n1 /= 10 );
  sprintf( cifra , "%s%u%s" , cad1 , k , cad2);
  for( i = 0 , j = 1 ; i <= x ; i ++ , j ++ ){
    if( 90 / j == k )
      putchar ( '\n' ) , j = 1 , lineas++;
    if( lineas == 38 )
      system ( "pause" ) , lineas = 0;
    printf( cifra , prims[i] );
  }
  /*************************************************************/
  free ( nums );
  free ( prims );
  return EXIT_SUCCESS;
}
 

Hago hincapié en el nuevo for, en lugar de:

Código C++:

i2 = i + i ;
    for( j = i * i ; j <= N ; j += i2 )
 

tengo que usar ahora:

Código C++:

for( j = z + z * i ; j <= N_medio ; j += i )
 

Todo es mirarlo un poco para entenderlo .

Y he aquí algunas salidas para alguno de los valores de N, en mi PC claro, en otros más nuevos y potentes se obtendrán mejores resultados:

Código C++:

..........................................................
        Hasta 100000000 hay 5761455 numeros primos
                El ultimo es: 99999989
  Process returned 0 (0x0)   execution time : 1.877 s
..........................................................
        Hasta 1000000000 hay 50847534 numeros primos
                El ultimo es: 999999937
  Process returned 0 (0x0)   execution time : 21.485 s
..........................................................
        Hasta 1500000000 hay 74726528 numeros primos
                El ultimo es: 1499999957
  Process returned 0 (0x0)   execution time : 32.334 s
..........................................................
        Hasta 2000000000 hay 98222287 numeros primos
                El ultimo es: 1999999973
  Process returned 0 (0x0)   execution time : 42.225 s
..........................................................
        Hasta 2500000000 hay 121443371 numeros primos
                El ultimo es: 2499999977
  Process returned 0 (0x0)   execution time : 54.648 s
..........................................................
        Hasta 2745000000 hay 132740843 numeros primos
                El ultimo es: 2744999969
  Process returned 0 (0x0)   execution time : 59.215 s
..........................................................
 

Y quedo a la espera de nuevas perspectivas amigo CalgaryCorpus.