ExistaPrimeDivImp

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;
}
%d bloggers like this: