Buna!
Pentru problema
#1149 ExistaPrimeDivImp
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
Am creat urmatorul program care functioneaza:
#include
using namespace std;
int eprim(int x)
{ int prim=1;
if (x<2)
prim=0;
if (x==2)
prim=1;
else
{
for (int i=2;i<=x/2;i++)
{
if (x%i==0)
{
prim=0;
}
}
}
return prim;
}
int div_prim (int v[100], int s, int d)
{
if (s==d)
return v[s];
else
{ int mij=(s+d)/2;
int a=div_prim(v,s,mij); ///vom scoate succesiv elementele din prima jumate a vectorului
int b=div_prim(v,mij+1,d); ///vom scoate succesiv elementele din a doua jumate a fectorului
return eprim(a)+eprim(b);
}
}
int main()
{
int n,v[100];
cin>>n;
for (int i=0;i
cin>>v[i];
if (div_prim(v,0,n-1)>0)
cout<<"DA";
else
cout<<"NU";
return 0;
}
Dar nu iau mai mult de 20 pct, oare ce are?
Răspunsuri la întrebare
Răspuns:
# include <iostream>
using namespace std;
int n, v[205];
void citire(int &n, int v[])
{
cin>>n;
for (int i=1; i<=n; i++)
cin>>v[i];
}
int prim(int v[], int st, int dr)
{
if(st == dr)
{
if(v[st]<2)
return 0;
if (v[st]>2 && v[st]%2==0)
return 0;
for (int d=3; d*d<=v[st]; d+=2)
if (v[st]%d==0)
return 0;
return 1;
}
else
{
int mij = (st + dr)/2;
int R1 = prim(v, st, mij);
int R2 = prim(v, mij+1, dr);
if( R1 || R2 )
return 1;
else
return 0;
}
}
int main()
{
citire(n, v);
if(prim(v, 1, n))
cout<<"DA";
else
cout<<"NU";
return 0;
}
Explicație: