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

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

//-------------------------------------------------
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 argc, char *argv[]) {
  int i, ipr, pr, nPrimi=0, nMax, n;
  char nomeFile[50];
  FILE * fp;

  if (argc < 2) {
    printf("\n  devi dare il nr max a riga di comando\n\n");
    return 0;
  }
  n = atoi(argv[1]);

  int v[n];
    
  sprintf(nomeFile, "numeri_primi_%d.txt", n);
  printf("I numeri primi andrannno scritti in %s\n", nomeFile);
  fp = fopen(nomeFile, "w");
  
  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++;  
      fprintf(fp, "%d\n", v[i]);
    }
  }
  
  printf("Totale numeri primi trovati: %d (max %d)\n", nPrimi, v[nPrimi-1]);

  fclose(fp);
  return 0;
}