#080 · Subiectul II · Programare

Să se verifice dacă numărul este prim

✓ Rezolvare explicatăDolj 2026 · nr. 3

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

Exersează mai departe

Probleme cu aceeași tehnică

#043ProgramareSă se calculeze şi să se afişeze cel mai mare divizor comun al elementelor vectorului #044ProgramareCel mai mare divizor comun a două numere, folosind o funcție recursivă #047ProgramareSă se afişeze două numere naturale prime a căror sumă este numărul n #064ProgramareSă se afişeze numărul valorilor prime din vector #066ProgramareSă se afişeze toate numerele mai mici sau egale cu n, care au exact 3 divizori #068ProgramareSă se afişeze numărul elementelor care sunt numere palindrom