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.

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 potevano 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.

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;
}

Alcuni link utili

Indice argomenti linguaggio C++

1- Introduzione al linguaggio C++

2- Variabili in C++

3- Operatori di assegnazione in C++

4- Esempi in C++

5- Casting in C++

Successione di Fibonacci in C++