Un număr natural se numește aproape prim dacă poate fi scris ca produs de două numere naturale prime distincte.

Cerinţa

Se citește un număr natural. Să se verifice dacă este aproape prim.

Date de intrare

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

Date de ieşire

Programul afișează pe ecran cuvântul DA, dacă n este aproape prim, respectiv NU în caz contrar.

Restricţii şi precizări

• 1 ≤ n ≤ 1.000.000.000

Exemplu 1:

Intrare

35

Ieșire

DA

Exemplu 2:

Intrare

50

Ieșire

NU

Explicație

35=5*7. 50 nu poate fi scris ca produs de două numere prime distincte.

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

int main ()
{
    int n;
    cin >> n;
    int cnt=0;
    for (int i = 1; i * i <= n; ++i)
    {
        if (i*(n/i)==n)
        cnt+=2;
        if (i*i==n)
        cnt--;
    }
    if (cnt==4)
    cout << "DA";
    else
    cout << "NU";
}