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

[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;
}