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

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