//numeri primi

#include <iostream.h>
#include <stdlib.h>

bool IsPrimeNumber(int n);
bool IsPrimeNumber2(int n);

int main() {
  int LastNum;

  do {
    cout << "Calcolo dei numeri primi fino a: ";
    cin >> LastNum;
  } while (LastNum <= 0);

  for (int i = 1; i <= LastNum; i++)
    if (IsPrimeNumber2(i))
      cout << i << "; ";

  cout << endl;

  system("PAUSE");
  return 0;
};

bool IsPrimeNumber(int n) {
// Sfrutta direttamente la definizione di numero primo:
// scarsamente efficiente

  // Controllo se il numero e' minore o uguale di zero:
  // numero non primo, uscita immediata.
  if (n <= 0) return false;

  // provo a dividere n per tutti i numeri da 2 a n-1;
  // se almeno una divisione ha resto nullo (divisibilità)
  // il numero non e' primo, uscita immediata.
  for (int i = 2; i < n; i++)
    if (n % i == 0) return false;

  return true;
};

bool IsPrimeNumber2(int n) {
// Versione piu' efficiente:
//   - rileva subito se n e' pari e diverso da 2: in quel caso non sarebbe primo;
//   - poi prova a dividere solo per i numeri dispari.
// Inoltre divide solo fino ad n/2 - 1: le successive divisioni
// sarebbero superflue.

  // Controllo se il numero e' minore o uguale di zero:
  // numero non primo, uscita immediata.
  if (n <= 0) return false;

  if (n <= 2) return true;
  
  //Controllo se n è pari. In questo caso il numero non è primo.
  if (n % 2 == 0) return false;

  for (int i = 3; i < n/2; i = i + 2)
    if (n % i == 0) return false;

  return true;
};

//Note:
//  si noti che i prototipi delle due funzioni IsPrimeNumber e
//  IsPrimeNumber2 sono identici dal momento che esse svolgono il
//  medesimo compito. Ciò che cambia è la loro implementazione.