/*
  Questo programma fa parte di una libreria messa a disposizione dei
  lettori del libro
  Alessandro Languasco & Alessandro Zaccagnini,
  Introduzione alla Crittografia, Ulrico Hoepli Editore, Milano, 2004.

  Crivello di Eratostene per la determinazione dei numeri primi "piccoli"
  Si veda il Paragrafo 6.3 del libro citato.
*/

#include <iostream>
#include <cmath>

/*
  Modificare il valore di queste due costanti in relazione alla
  quantità di memoria disponibile
*/
static const long
MASSIMO = 500000; // crivello l'intervallo [1, 2 * MASSIMO]

static const long
RADICE = 1000; // radice quadrata troncata di "2 * MASSIMO + 1"

/*
  Crivello di Eratostene
  "n_primi[]" è un array di `MASSIMO" booleani che rappresentano i
  numeri DISPARI da 1 a 2 * MASSIMO.
  La cella "i"-esima dell'array "n_primi[]" rappresenta l'intero
  dispari "2*i + 1".
  In questo modo si risparmiano le celle di memoria corrispondenti
  agli interi pari, al costo di qualche piccola complicazione di
  dettaglio.

  Questa funzione scrive i numeri primi trovati (uno per riga) nel
  file Primi.dat
*/

void
eratostene() {

  FILE *fp;
  fp = fopen("Primi.dat", "w");

  bool n_primi[MASSIMO] = {MASSIMO * false};

  std::cout << "Crivello" << std::endl;
  // Crivello con i numeri dispari nell'intervallo [3, RADICE]
  for(long i = 3; i < RADICE; i += 2)
    // Si comincia da "i*i", al quale corriponde l'elemento
    // (i*i-1)/2 dell'array "n_primi[j]"
    for(long j = (i * i - 1) / 2; j < MASSIMO; j += i)
      n_primi[j] = true;
  std::cout << "Fine crivello. Inizio conteggio... " << std::endl;

  // 1 non è un numero primo
  n_primi[0] = true;

  // 2 è un numero primo, ma, poiché è pari, non viene determinato
  // in questa versione del crivello, e deve essere inserito nella
  // lista esplicitamente
  std::cout << " 2";
  fprintf(fp, "2\n");

  long count = 1;
  for(long i = 0; i < MASSIMO; ++i)
    if (!n_primi[i]) {
      ++count;
      std::cout << "  " << 2 * i + 1;
      fprintf(fp, "%ld\n", 2*i+1);
      // Stampiamo sullo schermo 10 primi per riga
      if ((count % 10) == 0)
	std::cout << std::endl;
    }
  std::cout << std::endl << "Numero dei numeri primi trovati: ";
  std::cout << count << std::endl;
  fclose(fp);
}

int main() {

  eratostene();
}