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

[edumurru]

Os presento un código donde se aplica a la criba de Eratóstones. Es una forma de encontrar números primos. También hay una forma de aplicación por fuerza bruta:

Buscando números primos con la criba de Eratóstenes en C/C++: http://www.brainum.es/code/article/buscando-nmeros-primos-con-la-criba-de-eratstenes

[leosansan]

Tiene un fallo: declaras los arrays sin antes dimensionarlos.

Por otro lado se puede mejorar su eficiencia yendo del 3 a n de dos en dos, ya que los pares no son primos

Y si sólo se trata de imprimir, nos podríamos ahorrar el array prims.

El no uso de memoria dinámica limita bastante el valor máximo de n (en mi caso a 100000), cuando con malloc se podría llegar a 100000000.

Con el n corregido y sin prims:

Código C++:

#include <stdio.h>
#define N 100 /* hasta aqui calculamos los primos */
 
int main() {
  int i, j, nums[N+1],  x = 1;
  puts("\n\tSon PRIMOS:\n");
  printf( "\t%4d:::%5d\n", x++, 2 );
  for( i = 3; i <= N; i += 2 )
    if( nums[i] != 1 ) {
      printf( "\t%4d:::%5d\n", x++, i );
      for( j = 2; ( i * j ) <= N; j++)
        nums[i * j] = 1;
    }
  printf("\n  Hasta %d hay %d numeros primos\n", N, --x);
  return 0;
}
 

Sobre le Criba de Eratóstenes se puede mirar estos enlaces:

Criba de Eratóstenes

Criba de Eratóstenes Wikipedia

¡¡¡Saluditos!!!

[Pantaláimon]

El no uso de memoria dinámica limita bastante el valor máximo de n (en mi caso a 100000), cuando con malloc se podría llegar a 100000000.

Prueba de hacer la comparación así:

Código C:

j <= N/i
 

en vez de así:

Código C:

( i * j ) <= N
 

Y quizá puedas calcular más números.

[leosansan]

Iniciado por Pantaláimon

Prueba de hacer la comparación así:

Código C:

j <= N/i
 

en vez de así:

Código C:

( i * j ) <= N
 

Y quizá puedas calcular más números.

Lo tendré en cuenta "Gran Maestro".

Pero el problema radica en el tamaño del array:

Código C++:

nums[i * j]
 

Un fuerte saludo de tu más ferviente discípulo..... porque eres "tú", ¿verdad?. No se me ocurre que "otro" te halla tomado prestado el nick.

¡¡¡Saluditos!!!

[CalgaryCorpus]

Existe una correccion y unas optimizaciones posibles aun:
- nums deberia inicializarse, de otro modo la instruccion que compara su contenido (linea 9 en el post mostrado previamente) se encontrará con basura.
- El ciclo al interior multiplica 2 veces, una para comparar (linea 11), otra para asignar (linea 12).
Este par de multiplicaciones se puede reemplazar por 1 suma, debido a que el ciclo lo que hace es calcular los factores del numero i, es decir calcula 2*i, 3*i, 4*i, ... ( y asi sucesivamente ) y ese valor utiliza.

En vez de multiplicar todas las veces, se puede guardar el valor anterior y descubrir el siguiente sólo sumando i, asi (ver variable "multiplo"):

Código C++:

#include <stdio.h>
#include <memory.h>
#define N 100 /* hasta aqui calculamos los primos */
 
int main() {
  int i, multiplo, nums[N+1],  x = 1;
  // Importante inicializar el arreglo de marcas
  memset( nums, 0, (N + 1) * sizeof(int) );
  puts("\n\tSon PRIMOS:\n");
  printf( "\t%4d:::%5d\n", x++, 2 );
  for( i = 3; i <= N; i += 2 ) {
    if( nums[i] == 0 ) {
       printf( "\t%4d:::%5d\n", x++, i );
       for( multiplo = i+i; multiplo <= N; multiplo += i ) {
            nums[multiplo] = 1;
       }
    }
  }
 
  printf("\n  Hasta %d hay %d numeros primos\n", N, --x);
  return 0;
}
 

Se puede ver en ejecucion aqui: http://goo.gl/SqVW20

[leosansan]

Iniciado por CalgaryCorpus

...............................
Este par de multiplicaciones se puede reemplazar por 1 suma, debido a que el ciclo lo que hace es calcular los factores del numero i, es decir calcula 2*i, 3*i, 4*i, ... ( y asi sucesivamente ) y ese valor utiliza.

En vez de multiplicar todas las veces, se puede guardar el valor anterior y descubrir el siguiente sólo sumando i, asi (ver variable "multiplo"):
...............................

Bien observado lo de la multiplicaciónCalgaryCorpus, ya lo he puesto en práctica.

Y lo de inicializar fue un fallo de pasar un código previo, pero también bien observado.

Lo dejo con calloc para además de declarar, inicializar y con N de 10^8 con lo que tarda unos 7 segundos en mostrar el total de primos. Desactivo los printf para que "no pierda tiempo" en calcular el total de primos hasta N:

Código C++:

#include <stdio.h>
#include <stdlib.h>
#define N 100000000 /* hasta aqui calculamos los primos */
 
int main() {
  int i, j, z, x = 0;
  int  *nums = calloc( N+1, sizeof ( int ));
  int *prims = calloc( N+1, sizeof ( int ));
  ///puts("\n\tSon PRIMOS:\n");
  ///printf( "\t%4d:::%5d\n", x, 2 );
  prims[x] = 2;
  x++;
  for( i = 3; i <= N; i += 2 )
    if( nums[i] == 0 ) {
      prims[x] = i;
      ///printf( "\t%4d:::%5d\n", x, i );
      x++;
      for( j = ( i <= N ); ( z = ( i * j ) )  <= N; j+=2)
        nums[z] = 1;
    }
  /*for( i = 0; i < x; i ++ )
    printf( "%4d", prims[i] );*/
  printf( "\n  Hasta %d hay %d numeros primos\n\n", N, x );
  free ( nums );
  free ( prims );
  return 0;
}
}
 

EDITADO:

Mirándolo bien amigo CalgaryCorpus acabo de darme cuenta de un par de detalles. En tu for vas de multiplo = i+i con incrementos de multiplo += i.

Como ejemplo, supongamos para i los valores de 3 y de 5. Aplicándoles el for los valores que tomarían serían de:

3+3=6______5+5=10
+3=9-_____+5=15
+3=12_____+5=20
+3=15_____+5=25
+3=18_____+5=30
.....................

donde se observa que toman de forma inútil valores pares, que de antemano sabemos que no son primos y arrancan siempre con valor par al ser i+i. La forma de evitarlo sería con un paso de 2*i y un valor inicial de 3*i .

Y como ves tu intento de mejora para evitar la multiplicación de i * j se traduce en la introducción de nuevas multiplicaciones. Claro que al ser una de ellas de multiplicar por dos se podría optimizar más fácilmente.

En cualquier caso es de agradecer y motiva que haya gente por ahí que se moleste en mirar con tanto detenimiento los códigos. Gracias por la atención que le has prestado.

Un fuerte saludo.

[CalgaryCorpus]

El método de la criba asume que se quiere conocer los números primos y propone una manera de conocerlos.

Pienso que si se implementa haciendo suposiciones (como que los números pares no son primos (lo que es cierto, pero la idea del método es justamente hacer estos descartes en medio del funcionamiento, no en la implementación)), ya no se está enfrente de la implementación de ese método, sino de una optimización que el señor Eratostenes reclamaría como "impura"

Ahora, puesto que a optimizar hemos venido, y hacemos observaciones que permiten reducir el tiempo de ejecución, aquí una nueva versión que utiliza lo que indico:

- No es suficientemente óptimo partir desde 3*i el ciclo interno. El factor a aplicar debe ser el nro primo actual.
- Sumar 2i en cada vuelta no requiere multiplicar en cada vuelta, basta calcularlo 1 vez antes de iterar.

Con estas "mejoras" el calculo demora varios segundos menos. Si se cronometra la ejecución tanto del codigo enviado previamente enviado como éste, son notorias las diferencias.

Código C:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define N 100000000 /* hasta aqui calculamos los primos */
 
int main() {
  int i, j, z, x = 0;
  int i2;
  int *nums  = (int *) calloc( N+1, sizeof ( int ));
  int *prims = (int *) calloc( N+1, sizeof ( int ));
  ///puts("\n\tSon PRIMOS:\n");
  ///printf( "\t%4d:::%5d\n", x, 2 );
  prims[x] = 2;
  x++;
  int sq = (int) (sqrt(N) + 1);
 
  for( i = 3; i <= N; i += 2 ) {
    if( nums[i] ) continue;
 
    prims[x] = i;
    ///printf( "\t%4d:::%5d\n", x, i );
    x++;
 
    // no tiene sentido realizar los cálculos de abajo si estamos mas alla de la raiz de N
    if( i > sq ) continue;  
 
    i2 = i + i;
    // comenzar desde mas adelante, y sumar 2i cada vez
    for( j = i*i ; j <= N; j += i2) {  
        nums[j] = 1;
    }
  }
//  for( i = 0; i < x; i ++ ) printf( "%4d", prims[i] );
  printf( "\n  Hasta %d hay %d numeros primos\n\n", N, x );
  free ( nums );
  free ( prims );
  return 0;
}
 

[leosansan]

Iniciado por CalgaryCorpus

.........................................
Pienso que si se implementa haciendo suposiciones (como que los números pares no son primos (lo que es cierto, pero la idea del método es justamente hacer estos descartes en medio del funcionamiento, no en la implementación)), ya no se está enfrente de la implementación de ese método, sino de una optimización que el señor Eratostenes reclamaría como "impura"
.................................

.

Ahora me has convencido, ya había usado lo de sqrt en la clásica función esPrimo pero se me había pasado aquí.

Sólo quedaría por mejorar el que no "tache" más de una vez un número. Pero eso ya es otra historia....

¡Pero que diablos!, que todo sea por unas décimas de menos:

Código C++:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define N 100000000 /* hasta aqui calculamos los primos */
 
int main() {
  int i, j, x = 0, repes = 0;
  int i2, sq = (int) (sqrt(N) + 1);
  int *nums  = (int *) calloc( N+1, sizeof ( int ));
  int *prims = (int *) calloc( N+1, sizeof ( int ));
  ///puts("\n\tSon PRIMOS:\n");
  ///printf( "\t%4d:::%5d\n", x, 2 );
  prims[x] = 2;
  x++;
  for( i = 3; i <= N; i += 2 ) {
    if( nums[i] )
      continue;
    prims[x] = i;
    ///printf( "\t%4d:::%5d\n", x, i );
    x++;
    if( i > sq )
      continue;
    i2 = i + i;
    for( j = i * i ; j <= N; j += i2) {
      nums[j] ++;
      if ( nums[j] > 1 )
        repes += nums[j]-1;
        ///printf( "\ti=%4d:::j=%5d   nums[%3d] = %2d\n", i, j,j,nums[j] );
      while( ( j + i2 ) <= N && (nums[ j + i2 ] == 1 ) )
          j += i2;
    }
  }
  ///for( i = 0; i < x; i ++ ) printf( "%4d", prims[i] );
  printf("\n  Hasta %d hay %d numeros primos   repetidos = %d\n\n", N, x, repes);
  free ( nums );
  free ( prims );
  return 0;
}
 

Y otra vez gracias por la atención prestada.

¡¡¡Saluditos!!!

[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í:

Código C++:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define N 100000000 /* hasta aqui calculamos los primos */
 
int main() {
  int i, j, x = 0;
  int i2, sq = (int) (sqrt(N) + 1);
  bool *nums  = (bool *) calloc( N+1, sizeof ( bool ));
  int *prims = (int *) calloc( N+1, sizeof ( int ));
  ///puts("\n\tSon PRIMOS:\n");
  ///printf( "\t%4d:::%5d\n", x, 2 );
  prims[x++] = 2;
  for( i = 3; i <= N; i += 2 ) {
    if( nums[i] )
      continue;
    prims[x] = i;
    ///printf( "\t%4d:::%5d\n", x, i );
    x++;
    if( i > sq )
      continue;
    i2 = i + i;
    for( j = i * i ; j <= N; j += i2) {
      if( !nums[j] ) 
          nums[j] = true;
    }
  }
  ///for( i = 0; i < x; i ++ ) printf( "%4d", prims[i] );
  printf("\n  Hasta %d hay %d numeros primos\n\n", N, x );
  free ( nums );
  free ( prims );
  return 0;
}
 

Y esta version deberia tomar menos tiempo que todas las anteriores... creo
Al menos en mis pruebas, asi es

[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.

[Pantaláimon]

No me acordaba que había participado aquí. Con lo que me gustan las frikadas numéricas. Aquí una vuelta de tuerca al algoritmo sin perder la esencia (ansi C):

Código C:

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
 
int main(void) {
   unsigned top = 1000000000;
   unsigned rtop = sqrt(top);
   unsigned char* nums = calloc( top, sizeof *nums);
   unsigned primsTop = 2.2 * (top / log(top)); /* apaño para ahorrar memoria */
   unsigned* prims = calloc( primsTop, sizeof *prims);
   unsigned n; /* contador primos */
   unsigned i, i2, ii;
   unsigned j, k, l, x;
 
   k = x = nums[4] = nums[6] = nums[8] = 1;
   i = l = n = prims[0] = 2;
   prims[1] = 3;
   l = 5;
   i2 = i + i;
   ii = i * i;
 
   /* calculo de la tabla */
   for (i = 3; i <= rtop; i += 2, i2 += 4) {
      /* El primer primo de la tabla es el primero con valor 0 */
      if(nums[i]) continue;
 
      /* todo numero j tal que l <= j <= i*i-1 con nums[j] == 0 es primo */
      ii = i*i;
      for (j = l; j < ii; j += 2 )
         if(nums[j] == 0)
            prims[n++] = j;
      l = ii+2;
      
      /* Dado k que va de x a n-1, se descartan los compuestos i*prims[k]    *
       * donde se ve que i == prims[x]                                       *
       * (Es una forma de evitar descartar números que ya están descartados) */
      for (k = x; k < n; ++k) {
         j = i*prims[k];
         if (j >= top) break;
         nums[j] = 1;
      }
     
      /* a partir de aquí, se descartan los compuestos de la manera común */
      if (j < top) j += i2;
      for (; j < top; j += i2) {
         if(!nums[j])
            nums[j] = 1;
      }
      ++x;
   }
 
   /* calcular resto de primos */
   for (i = prims[n-1]+2; i < top; i += 2) {
      if (nums[i] == 0) {
         ++n;
         /* prims[n++] = i; */
      }
   }
   
   printf("%d primos\n", n);
   free(nums);
   free(prims);
 
   return 0;
}
 

Un saludo!

[leosansan]

Iniciado por Pantaláimon

No me acordaba que había participado aquí. Con lo que me gustan las frikadas numéricas. Aquí una vuelta de tuerca al algoritmo sin perder la esencia (ansi C):
.................................................. ......
Un saludo!

No sé por qué extraño motivo no me compila declarando la variable "top" como unsigned, he de declararla como int.

La salida para los 100 primeros primos no es la esperada:

Código C++:

24 primos
  2  3  5  7 11 13 17 19 23 27 31 39 43 47  0  0  0  0  0  0  0  0  0  0
Process returned 0 (0x0)   execution time : 0.040 s
Press any key to continue.
 

"Creo" que son 25, pero eso no es más que un ajuste mínmo. Lo raro es que a partir del 47 son todos ceros

Como todos tus códigos requiere de un examen más minucioso a ver que sucede.

Por cierto, la aproximación que usas para limitar la memoria de los "prims" es demasiado "generosa". Como ejemplo para los 100 primeros números da un valor de 48, cuando en realidad son tan solo 25 tal como lo "clava" la relación que uso en mi código, y de CalgaryCorpus por supuesto.

Y ya para 100000000 ni te cuento, da 9375126 primos cuando en realidad son "5761455" con lo que el ajuste no ha de ser tan mínimo como creí en un principio.

Creo que tienes que "afinarlo" un poquitín.

Bueno lo miraré más detenidamente.

¡¡¡Saluditos!!!



Y por cierto, bienvenido otra vez.

[Pantaláimon]

Vaya! Quizá no testeé suficiente. Esta tarde cuando tenga un rato lo reviso.

La aproximación la saqué de aquí y le puse una constante multiplicativa para que nunca fuera menor que el número -al parecer erróneo- de primos que me daba para las pruebas que hice. Como es una aproximación asintótica, en teroía debería ajustarse un poco más cuando el número de primos a analizar es más grande.

Un saludo!

[leosansan]

Iniciado por Pantaláimon

Vaya! Quizá no testeé suficiente. Esta tarde cuando tenga un rato lo reviso.

La aproximación la saqué de aquí y le puse una constante multiplicativa .................................................. ..

Lo imaginaba, lo de la aproximación. Fui más practico y busqué la relación o ciente entre el número y los primos que correspondían, por eso mi relación es tan ajustada.

Quedo, ansioso eso sí, a la espera de tus mejoras, "¡ fenómeno !".

¡¡¡Saluditos!!!

[Pantaláimon]

Vaya, era la variable i2, que debería tener en todo momento el valor de 2*i pero no lo tuvo por un despiste. El código ahora apenas mejora el tuyo en velocidad:

Código C:

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
 
int main(void) {
   unsigned top = 1000000000;
   unsigned rtop = sqrt(top);
   unsigned char* nums = calloc( top, sizeof *nums);
   unsigned primsTop = 1.2 * (top / log(top)); /* apaño para ahorrar memoria */
   unsigned* prims = calloc( primsTop, sizeof *prims);
   unsigned n; /* contador primos */
   unsigned i, i2, ii;
   unsigned j, k, l, x;
 
   k = x = nums[4] = nums[6] = nums[8] = 1;
   l = n = prims[0] = 2;
   i = prims[1] = 3;
   l = 5;
   i2 = i + i;
   ii = i * i;
 
   /* calculo de la tabla */
   for (i = 3; i <= rtop; i = prims[x], i2 = 2*i) {
 
      /* todo numero j tal que l <= j <= i*i-1 con nums[j] == 0 es primo */
      
      ii = i*i;
      /* printf("A) calcula primos de %d a %d\n", l, ii-1); */
      for (j = l; j < ii; j += 2)
         if(nums[j] == 0){
            prims[n++] = j;
            //printf("%d\n", prims[n-1]);
         }
      l = ii+2;
      
      /* Dado k que va de x a n-1, se descartan los compuestos i*prims[k]    *
       * donde se ve que i == prims[x]                                       *
       * (Es una forma de evitar descartar números que ya están descartados) */
      /* printf("B) descartar primos de %d a %d\n", i*prims[x], i*prims[n-1]); */
      for (k = x; k < n; ++k) {
         j = i*prims[k];
         if (j >= top) break;
         nums[j] = 1;
         /* printf("%d\n", j); */
      }
     
      /* a partir de aquí, se descartan los compuestos de la manera común */
 
      if (j < top) j += i2;
      /* printf("C) descartar primos de %d a %d\n", j, top-1); */
      for (; j < top; j += i2) {
         if(!nums[j]) {
            nums[j] = 1;
            /*printf("%d\n", j);*/
         }
      }
      ++x;
      //printf("%d\n", prims[x]);
   }
 
   /* calcular resto de primos */
   for (i = prims[n-1]+2; i < top; i += 2) {
      if (nums[i] == 0) {
         prims[n] = i;
         ++n;
      }
   }
   /*
   for(i = 0; i < n; ++i) {
      printf("%d, ", prims[i]);
   }
   */
   printf("%d primos\n", n);
   printf("%f\n", (double)n/primsTop);
   free(nums);
   free(prims);
 
   return 0;
}
 

Edit: añadida nueva modificación que mejora unas décimas.

Un saludo!