Numeri primi in C++, contare quanti numeri primi in C++

Sviluppiamo un programma sui numeri primi in C++, utilizzando i cicli for, while e do-while spiegati nelle scorse lezioni.

Primo esempio – Numeri primi in C++

Inserire un numero e verificare se può essere un numero primo.

Innanzitutto pensiamo alle variabili che ci servono e le dichiariamo:

n – Il numero da verificare.

div – Il divisore del numero.

i – La variabile contatore del ciclo dor.

conta – Una variabile che conta i divisori.

Dopo aver dichiarato le variabili, assegniamo a div il valore 1, cioè partiamo a dividere per 1. Alla variabile conta assegniamo il valore 0.

Poi chiediamo all’utente di inserire un numero.

Per controllare se è primo realizziamo un ciclo while che termina quando il divisore è minore o uguale alla metà del numero, in quanto dividere un numero per una quantità maggiore della sua metà dà comunque un numero con la virgola. Possiamo anche impostare un’altra condizione in modo da risparmiare molto più tempo, ovvero quando il contatore raggiunge 2.

Scatena il tuo potenziale con ’50 Algoritmi per imparare C++’, il libro appena lanciato su Amazon che ti guiderà nel mondo della programmazione con passione e precisione!

Acquistalo su Amazon

Infatti un numero primo ha come divisore 1 e se stesso, quindi in tutto ha due divisori. Dato che nell’algoritmo non divideremo il numero per se stesso allora, appena il contatore diventa 2, usciremo dal ciclo, in quanto siamo sicuri che il numero non può essere primo.

Al termine se conta vale 1, cioè se ha trovato solo un divisore, allora il numero è primo.

Ecco dunque l’algoritmo sui numeri primi in C++:

int main() {
    int n, div = 1, conta = 0;

    do {
        cout << "Inserisci un numero: ";
        cin >> n;
    } while (n < 1);

    while (conta <= 1 && div <= n / 2) {
        if (n % div == 0) {
            // se trova divisori incrementa il contatore dei divisori
            conta++;
        }
        div++;
    }

    if (conta == 1) {
        cout << "Il numero è primo\n";
    } else {
        cout << "Il numero non è primo\n";
    }

    return 0;
}

Chiaramente possono esserci tante altre soluzioni, proponete pure la vostra.

Secondo esempio

Il secondo esempio in realtà è una variante del primo.

Inserire N numeri e contare quanti numeri primi sono stati inseriti.

Chiediamo di inserire N e facciamo un controllo dell’input.

Dopo utilizziamo un ciclo for per inserire gli N numeri. Per ogni numero verifichiamo se è primo con lo stesso metodo dell’esercizio 1.

Poi controlliamo se conta è uguale a 1. Se vero, allora il numero è primo e incrementiamo dunque il contatore dei numeri primi.

Riportiamo i valori di conta e div alla situazione iniziale e continuiamo a iterare. Al termine visualizzo il contatore dei numeri primi.

Scatena il tuo potenziale con ’50 Algoritmi per imparare C++’, il libro appena lanciato su Amazon che ti guiderà nel mondo della programmazione con passione e precisione!

Acquistalo su Amazon

Ecco dunque l’algoritmo completo sui numeri primi in C++:

#include <iostream>
using namespace std;

int main() {
    int n, N, div = 1, conta = 0, contaprimi = 0;

    do {
        cout << "Quanti numeri vuoi inserire? : \t";
        cin >> N;
    } while (N <= 0);

    for (i = 0; i < N; i++) {
        cout << "Inserisci un numero: ";
        cin >> n;
        
        while (conta < 3 && div <= n / 2) {
            if (n % div == 0)
                conta++;
            div++;
        }
        
        if (conta == 1) {
            contaprimi++;
        }
        conta = 0;
        div = 1;
    }

    cout << "I numeri primi inseriti sono: " << contaprimi;

    return 0;
}

Lezione precedente: esercizi con il for in C++

Lezione successiva: massimo dei numeri pari e dispari