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

[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