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
Solutie
#include <iostream>
using namespace std;
bool prim(int n)
{
int d;
if(n<=1) return 0;
if(n%2==0&&n!=2) return 0;
for(int d=3;d*d<n;d+=2)
{
if(n%d==0) return 0;
}
return 1;
}
int v[1005];
int divimp(int st,int dr)
{
if(st==dr)
{
if(prim(v[st])==1)
return 1;
else
return 0;
}
else
{
int m=(st+dr)/2;
int p1=divimp(st,m);
int p2=divimp(m+1,dr);
return p1+p2;
}
}
int main()
{
int n,st,dr;
cin>>n;
st=0;
dr=n-1;
for(int i=0;i<n;i++)
{
cin>>v[i];
}
if(divimp(st,dr)>=1)
cout<<"DA";
else cout<<"NU";
return 0;
}