282
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; }
Comentarii