Question

Prezentati algoritmul de verificare a primalitatii unui numar, dupa urmatorul plan de idei

-descriere in limbaj natural si exemplificare a etapelor algoritmului pentru un numar mai mare decat 50;

-apreciere a complexitatii algoritmului, din punct de vedere al duratei de executare

-exemplificare printr-o problema concreta, in a carei rezolvare se utilizeaza algoritmul ales( enunt, implementare in limbaj de programare a unei solutii, descriere a solutiei).

Answer 1

Un posibil algoritm pentru a rezolva eficient primalitatea unui număr poate fi asta :

bool prim(int x)

{

if (x < 2)

return false;

for (int d = 2; d <= sqrt(x) ; d++)

if (x % d == 0)

return false;

return true ;

}

Funcția are proprietatea de a parcurge posibilii divizori ai lui x într un timp mult mai scrurt decât prin metoda clasica pana la n / 2.

Complexitate O(sqrtn)