Question

Cerința
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

Answer 1

Răspuns:

#include <iostream>

using namespace std;

bool e_prim(int n) {

if (n < 2) return false;

if (n == 2)  return true;

if (n % 2 == 0) return false;

for (int d = 3; d * d <= n; d += 2)

 if (n % d == 0) return false;

return true;

}

int maxim_prim_divImp(int v[], int i, int s) {

if (i == s) {

 if (e_prim(v[s])) return v[s];

 return 0;

}

int d1 = maxim_prim_divImp(v, i, (i + s) / 2);

int d2 = maxim_prim_divImp(v, (i + s) / 2 + 1, s);

if (d1 > d2)

 return d1;

return d2;

}

int main() {

int n, v[1001],M,s=1;

cin >> n;

for (int i = 1; i <= n; i++)

 cin >> v[i];

M=maxim_prim_divImp(v,1,n);

   cout<<M;

return 0;

}

Explicație:

100 p pb info