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

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