/*  implementazione del crivello di Eratostene 
    per la ricerca dei numeri primi
*/

#include <stdio.h>
#include <math.h>

#define N 1000

//-------------------------------------------------
void rimuoviZeriI(int *pn, int v[]) {
  int i, nnz = 0;

  for (i=0; i < *pn; i++) {
    if (v[i] != 0) {
      v[nnz++] = v[i];
    }
  }
  *pn = nnz;
}
  
//--------------------------------------------------
int main() {
  int i, ipr, pr, nPrimi=0, nMax, n=N, v[N];
  
  for(i=0; i<n; i++) v[i]=i+1;

  ipr  = 1;                 // indice del primo numero primo != 1  (-> 2)
  nMax = floor( sqrt(n));   // massimo nr con cui provare
  while (ipr < nMax) {
    pr = v[ipr];
    if(pr != 0) {           // se non è già stato cancellato è primo
      for(i=(ipr+1); i<n; i++){
        if( !(v[i]%pr) ) {
          v[i] = 0;
        }
      }
    }
    ipr++;  
  }

  rimuoviZeriI(&n, v);
  
  for(i=0; i<n; i++) {
    if(v[i] !=0) {
      nPrimi++;  
      printf("%d ", v[i]);
    }
  }
  puts("\n");
  printf("Totale numeri primi trovati: %d (Max %d)\n", nPrimi, v[n-1]);
  
  return 0;
}