L10. Algoritmi fundamentali. Divizibilitate. N este prim?

Divizibilitate

Problema. Pentru un N dat, care sunt divizorii lui N?

Multimea divizorilor lui N este cuprinsa intre valorile 1 si N. Un numar D este divizor al lui N daca N se imparte exact la D. Pentru noi, impartirea exacta inseamna ca restul impartirii lui N la D este zero. Trebuie sa cautam acele valori intre 1 si N la care N se imparte exact. Vom aifsa si vom numara aceste valori.

natural N, D, NR;
NR=0;
citeste N;
pentru D=1, N executa 
               daca (N%D==0) atunci { scrie D; NR=NR+1}
scrie NR;

Cu numarul de divizori putem stabili daca numarul N este prim.

daca (NR==2) atunci scrie N, " este prim!"

Este N numar prim?

Problema. Fie N un numar natural. Este N numar prim?

Conform matematicii un numar N este prim daca are drept divizori pe 1 si pe N.

Varianta 1. Ideea este sa realizam cat mai putine teste, astfel incat algoritmul sa se incheie mai repede

• D=2;


• cat timp (D<=N-1 si N%D!=0) executa D=D+1;


• daca (N%D==0) atunci scrie  "divizibil"


• altfel scrie "prim"

Am redus doua teste : nu mai testam cazul D=1 si D=N. De asemenea, profitam de situatia in care gasim primul divizor pentru a iesi din repetitie. Totusi, pentru cazul in care numarul ar fi prim, inca se executa N-2 pasi.

Varianta 2. Numarul 2 este cel mai mic potential divizor. Deduc ca numarul N/2 este cel mai mare potential divizor.

• D=2;


• cat timp (D<=N/2 si N%D!=0) executa D=D+1;


• daca (N%D==0) atunci scrie  "divizibil"


• altfel scrie "prim"

In aceasta varianta se executa, in cel mai rau caz, N/2 operatii. Super! Am redus munca la jumatate! Se poate mai bine?

Varianta 3. Sa cercetam, in continuare, perechile de potential divizori: 2 cu N/2, 3 cu N/3, 4 cu N/4, .... Observ ca pe masura ce primul termen creste, al doilea scade. Deduc ca, la un moment dat cei doi termeni pot fi egali. Adica ar putea fi un element X astfel incat N==X*X sa fie adevarat! In consecinta X=radical(N) . Deci ultima pereche care ar trebui studiata este cea cu radical (N).

• D=2;


• cat timp (D<=radical(N) si N%D!=0) executa D=D+1;


• daca (N%D==0) atunci scrie  "divizibil"


• altfel scrie "prim"

Este cert ca radical(N)<N/2. Iata ca am obtinut un numar mai mic de operatii. Sa cercetam cat de eficienti sunt  algoritmii nostri.

Numarul N=611953 este prim, spun unii.

• varianta 1 va executa 611951 pasi


• varianta 2 va executa 305 976 pasi


• 
  

  varianta 3 va executa 782 pasi!!!!!!!

  
  

E ceva, nu?