Cerinţa

Să se scrie un program care citește de la tastatură un număr natural n și verifică dacă este prim.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieşire

Programul afișează pe ecran mesajul DA, dacă n este număr prim, respectiv NU în caz contrar.

Restricţii şi precizări

• 0 ≤ n ≤ 1.000.000.000
• un număr natural este prim dacă are exact doi divizori distincți: 1 și el însuși.

Exemplu

Intrare

17

Ieșire

DA

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int d = 2;
    int nrdiv = 1;
    while(n > 1){
        int p = 0;
        while(n % d == 0)
            n /= d, p++;
        nrdiv = nrdiv * (p + 1);
        d++;
        if(d * d > n)
            d = n;
    }
    if(nrdiv != 2)
        cout << "NU";
    else
        cout << "DA";
    return 0;
}