#080Programare

Să se verifice dacă numărul este prim

Enunț

Se citeşte n, număr natural, de la tastatură. Să se verifice dacă numărul este prim. În caz afirmativ se va afişa mesajul DA, iar în caz contrar mesajul NU şi divizorii acestuia, ca în exemplul de mai jos.

Exemple

Date de intrare	Date de ieșire	Explicații
`71`	`DA`	71 nu se împarte exact la niciun număr între 2 și 8
`20`	`NU` `Divizorii: 1 2 4 5 10 20`	20 are și alți divizori în afară de 1 și 20

Rezolvare

C++

#include <iostream>
using namespace std;

bool estePrim(int n) {
    if (n < 2) return false;            // 0 si 1 nu sunt prime
    for (int d = 2; d * d <= n; d++)
        if (n % d == 0) return false;   // am gasit un divizor -> nu e prim
    return true;
}

int main() {
    int n;
    cin >> n;

    if (estePrim(n)) {
        cout << "DA";
    } else {
        cout << "NU" << endl << "Divizorii:";
        for (int d = 1; d <= n; d++)
            if (n % d == 0) cout << " " << d;
    }
    return 0;
}

Cum funcționează

Un număr este prim dacă are exact doi divizori: 1 și el însuși. Deci ca să demonstrezi că n nu e prim, e suficient să găsești un singur divizor între 2 și n-1.

Verificarea stă pe n % d == 0 — testul de divizibilitate pe care se sprijină aproape toate problemele din categoria asta: restul împărțirii lui n la d este 0 exact când d îl împarte exact pe n.

Partea importantă e condiția de oprire, d * d <= n. Nu e nevoie să cauți divizori până la n, pentru că divizorii vin în perechi. Pentru n = 36:

1 × 36        6 × 6        ← mijlocul, adica radical din 36
2 × 18
3 × 12
4 × 9

Fiecare divizor mai mare decât √n are deja o pereche mai mică decât √n. Dacă n-ai găsit niciun divizor până la √n, nu mai există niciunul nici după. Pentru n = 1.000.000 asta înseamnă 1000 de pași în loc de un milion.

La afișarea divizorilor bucla merge însă până la n, pentru că acolo chiar îi vrem pe toți, inclusiv 1 și n.

Greșeli frecvente

for (int d = 2; d <= n; d++) la verificare — când d ajunge la n, condiția n % d == 0 e adevărată (orice număr se împarte la el însuși), deci funcția returnează false pentru orice număr. Bucla trebuie să se oprească înainte de n.
Uitarea cazului n < 2 — fără el, 1 este raportat ca prim, pentru că bucla nu se execută niciodată și se ajunge direct la return true. 1 nu este prim.
sqrt(n) în loc de d * d <= n — merge, dar sqrt lucrează cu numere reale și poate da 5.999999 în loc de 6, ratând ultimul divizor. Cu d * d rămâi pe numere întregi, exact.
return true pus în interiorul buclei — funcția iese la primul d care nu divide, deci răspunde „prim" aproape întotdeauna. return true se scrie după buclă.

Apariții

Dolj 2026 — problema 3 · sursa oficială