Se consideră un șir cu n elemente, numere naturale. Folosind metoda Divide et Impera, determinați cel mai mare element prim din acest șir.
Date de intrare
Programul citește de la tastatură numărul n, iar apoi cele n elemente ale șirului.
Date de ieșire
Programul va afișa pe ecran numărul M, cel mai mare element prim al șirului.
Restricții și precizări
1 ≤ n ≤ 1000
elementele șirului vor fi mai mici decât 1.000.000
se garantează că în șir apare cel puțin un element prim
se recomandă folosirea metodei Divide et Impera
Exemplu
Intrare
6
4 1 8 4 3 5
Ieșire
5
SOLUTIE
#include <iostream>
using namespace std;
bool prim(int n)
{
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 maxprim(int st,int dr)
{
if(st==dr)
{
return v[st];
}
else
{
int m=(st+dr)/2;
int a=maxprim(st,m);
int b=maxprim(m+1,dr);
if(prim(a)&&prim(b))
return max(a,b);
else if(prim(a))
return a;
else if(prim(b))
return b;
}
}
int main()
{
int n,st=0,dr;
cin>>n;
dr=n-1;
for(int i=0;i<n;i++)
{
cin>>v[i];
}
cout<<maxprim(st,dr);
return 0;
}