RSS

L10. Algoritmi fundamentali. Divizibilitate. N este prim?

05 Mar

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 D astfel incat N==D*D sa fie adevarat! In consecinta X=radical(N) . Deci ultima pereche care ar trebui studiata este cea cu radical (N) (putem scrie D<=N/D, valoarea intreaga, cea mai apropiata de radical(N)).

  • D=2;
  • cat timp (D<=N/D 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 maxim 611951 pasi
  • varianta 2 va executa maxim  305 976 pasi
  • varianta 3 va executa maxim 782 pasi!!!!!!!

E ceva, nu?

Varianta 4. Si inca mai merge…

  • daca (N==2) atunci scrie “prim”
  • altfel daca (nN%2==0 ) atunci scrie “divizibil”
  • altfel {
    • D=3;
    • cat timp (D<=N/D si N%D!=0) executa D=D+2;
    • daca (N%D==0) atunci scrie  “divizibil” altfel scrie “prim”
    • }

Algoritmul de mai sus verifica daca N este 2 si elimina din discutie numerele pare. Pentru ca majoritatea numerelor prime sunt impare, parcurg numai valorile impare si le intreb daca nu cumva sunt divizori pentru N.

Varianta 4 va efectua maxim 390 pasi pentru N=611953.

 
6 Comments

Posted by on 05/03/2012 in C2_1. Algoritmica

 

Tags: , , , , , ,

6 responses to “L10. Algoritmi fundamentali. Divizibilitate. N este prim?

  1. Rallu Ralucca

    18/12/2013 at 19:08

    cum ar arata un algoritm care numara numarul de divizori ai lui N?

     
  2. mchelariu71

    19/12/2013 at 23:12

    e prima problema. cu asta am inceput

     
  3. Mica Radu

    12/09/2016 at 01:56

    Buna seara!

    Pentru variantele 1 si 2 de la problema 2, as avea o intrebare:
    Avand in vedere ca inainte de a se iesi din repetitie variabila D se incrementeaza, este posibil ca pentru D=N-1, valoare ce inca respecta conditia (D<=N-1 si N%D!=0), dupa executarea D++, sa se ajunga la D=N?
    In acest caz, dupa iesirea din repetitie, nu vom primi mereu rezultatul “divizibil”, chiar si pentru numerele prime?
    Pentru a face algoritmul sa functioneze corect, trebuit sa adaug urmatoarea conditionare pentru expresia"if": if(d<=n-1&&n%d==0) cout<<"Numarul "<<n<<" este divizibil"<<endl;
    else cout<<"Numarul "<<n<<" este prim"<<endl;
    Va multumesc!

     
  4. Mica Radu

    12/09/2016 at 03:16

    De asemenea, la Varianta 4, pentru N=3, din algoritm ar rezulta ca N este divizibil;
    N!=2 – se trece la verificarea 2.
    2%2!=0 – se trece la verificarea urmatoare.
    3>=rad(3) – se sare peste repetitie si se ajunge la
    3%3==0 – Numarul este divizibil.

    Imi cer scuze daca am gresit.

    Cu stima,

    Radu

     
  5. mchelariu71

    12/09/2016 at 06:56

    Radu, instructiunea cat_timp/while intai intreaba si apoi executa, motiv pentru care nu se mai face nici o incrementare daca conditia de iesire este satisfacuta.
    Am sa verific si varianta 4. Multumesc!

     
  6. Radu Mica

    12/09/2016 at 22:26

    Ah, ok. Am avut impresia ca sunt instructiuni separate, si ca “daca (N%D==0) atunci scrie “divizibil”” se executa dupa ce se iese din repetite. Imi cer scuze.

    Cu stima,

    Radu

     

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: