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

[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