Număr prim – numărăm divizorii

Enunț

Se citeşte un număr natural n. Să se verifice dacă n este sau nu un număr prim.

Exemplu

Dacă n = 7, atunci algoritmul va afişa DA pentru că divizorii lui 7 sunt 1 și 7, deci 7 este număr prim.

Dacă n = 8, atunci algoritmul va afişa NU pentru că divizorii lui 8 sunt 1, 2, 4, 8,deci 8 nu este număr prim.

Descrierea metodei de rezolvare

Putem folosi proprietatea “Un număr prim este un număr natural, mai mare decât 1, care are exact doi divizori: numărul 1 și numărul în sine.“

Inițializare: Vom inițializa o variabilă contor (de exemplu, nrDiv) care va număra câți divizori are numărul n.

Parcurgerea divizorilor: Vom parcurge toate numerele de la 1 până la n și pentru fiecare număr d, verificăm dacă n este divizibil cu d (adică dacă n % d == 0). Dacă este divizibil, incrementăm contorul nrDiv.

Verificarea rezultatului: Dacă la finalul parcurgerii contorul nrDiv este egal cu 2, atunci n este un număr prim (deoarece doar 1 și n sunt divizori ai săi). Dacă nrDiv este mai mare decât 2, n nu este prim.

Algoritmul în limbaj pseudocod

Algoritmul în limbaj de programare C/C++

/************************************************

numar prim - V1 numaram divizorii

**************************************************/
#include <iostream>
using namespace std;

int main() {
    int n;
    int nrDiv = 0;

    cout << "Introduceti un numar: ";
    cin >> n;

    // Parcurgem toate valorile posibile ale lui d de la 1 la n
    for (int d = 1; d <= n; d++) {
        // Verificam daca d este un divizor al lui n
        if (n % d == 0) {
            nrDiv++;
        }
    }

    // Verificam daca numarul are exact 2 divizori (1 si n)
    if (nrDiv == 2) {
        cout << "DA" << endl;  // n este numar prim
    } else {
        cout << "NU" << endl;  // n nu este numar prim
    }

    return 0;
}