Cerinţa

Se dă un şir cu n elemente, numere naturale. Folosind metoda Divide et Impera să se verifice dacă în şir există elemente prime.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n elemente ale şirului.

Date de ieşire

Programul afișează pe ecran mesajul DA, dacă şirul conţine elemente prime, respectiv NU în caz contrar.

Restricţii şi precizări

• 1 ≤ n ≤ 200
• elementele şirului vor fi mai mici decât 1.000.000.000

Exemplu

Date de intrare

5
21 8 6 10 8

Date de ieșire

NU

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

bool prim(int n){
    int cnt = 1, d = 2;
    while(n > 1){
        int p = 0;
        while(n % d == 0)
            n /= d, p++;
        cnt *= (p + 1);
        d++;
        if(d * d > n)
            d = n;
    }
    return cnt == 2;
}

bool exista_prime(int a[], int st, int dr){
    if(st == dr)
        return prim(a[st]);
    else{
        int mij = (st + dr) / 2;
        return exista_prime(a, st, mij) || exista_prime(a, mij + 1, dr);
    }
}

int main()
{
    int n, a[201];
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];

    if(exista_prime(a, 1, n))
        cout << "DA";
    else
        cout << "NU";

    return 0;
}