Blog

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