Stampare i numeri primi inferiori ad uno letto in input

Un esercizio classico col c++ che trova i numeri primi inferiori ad una soglia letta in input. In questa versione utilizziamo una funzione che restituisce vero/falso se un numero come parametro è primo.

Il cuore del problema è trovare se un numero è primo o meno con una funzione, così da poter creare un ciclo che successivo che alimenta la funzione e torna il risultato in modo da procedere o meno alla stampa sempre dal programma principale.

Quando siamo di fronte ad un problema matematico, è sempre bene fare degli esempi numerici o partire dalle definizioni per capire come trasformarle poi in codice. In particolare un numero è primo quando è divisibile solo per se stesso e per l’unità. Quindi per approcciare in modo semplice il problema potrei contare quanti numeri dividono il numero da analizzare e valutare se sono solo due, se stesso e l’unità, o più. Nel primo caso avremo trovato che è primo!

#include <iostream>
using namespace std;

bool numeroprimo(int num)
{
  int cont=0;
  for (int i = 1 ;i <= num; i++)
  {
    if (num % i == 0)
      cont++;
  }
  
  if (cont == 2)
    return true;
  
  return false;
}

int main() 
{
  int n;
  cout << "|----------------------------|" << endl;
  cout << "|     STAMPA NUMERI PRIMI    |"<<endl;
  cout << "|----------------------------|" << endl;
  
  do 
  {
    cout<<"inserire il numero limite ";
    cin>>n;
  }
  while (n < 0);

  for (int i = 1; i < n; i++)
  {
     if (numeroprimo (i) == true)
    cout<<"il numero "<<i<<" è primo"<<endl;
  }
  
  return 0;
}

In realtà si può ulteriormente semplificare: i divisori di un numero sono solo nella sua prima metà, quindi paradossalmente il nostro controllo potrebbe partire da 2, visto che 1 è un divisore banale ed arrivare a cercare divisori fino a n/2 con n il numero da controllare. A questo punto basta trovare un numero che divide per essere sicuri che il numero non sia primo e tornare direttamente falso, altrimenti se non avremo trovato divisori potremo tornare vero che è un numero primo.

La seconda versione ottimizzata della funzione:

bool numeroprimo(int num)
{
  int cont=0;
  for (int i = 2 ;i <= num/2; i++)
  {
    if (num % i == 0)
      return false;
  }
  
  return true;
}

Ultima modifica 26 Agosto 2022