Numere prime in Pascal

25 Mai

Am primit cateva intrebari legate de numere prime in Pascal. Raspunsul se alfa prin comentarii, dar pentru cei care nu au timp sa caute m-am gandit sa dezvolt ideea intr-un tutorial.

Sa pornim de la un exemplu clasic de problema cu numere prime: este numarul a numar prim?

Sa vedem cum trebuie sa gandim problema… un numar prim nu are niciun divizor in afara de 1 si de el insusi. Cea mai simpla metoda este sa verificam toate numerele de la 2 la numar-1 si daca restul impartirii numarului la oricare dintre aceste valori este diferit de 0, atunci numarul nu este prim.

In pseudocod, algoritmul arata asa:

citeste nr
ok = true
pentru  i = 2 pana la nr-1 executa
     daca nr mod i = 0 atunci
          ok = false
daca ok = true atunci
     scrie "este numar prim"


Consideram o variabila de tip boolean care va face verificarea pentru noi: pornim de la premiza ca numarul este prim, iar daca restul impartirii lui la una dintre valorile din intervalul (2; n-1) este egal cu 0, atunci variabila boolean devine false si concluzionam ca numarul nu este prim.

Sa vedem cum arata algoritmul de verificare daca un numar peste prim in Pascal:

read(nr);
ok := true;
for i := 2 to nr-2 do
     if nr mod i = 0 then
          ok := false;
if ok = true then
     write("Numarul ", nr, " este prim")
else 
     write("Numarul ", nr, " NU este prim");

Putem sa inlocuim loop-ul for cu un loop while:

read(nr);
ok := true;
i := 2;
while i < nr begin
     if nr mod i = 0 then
          ok := false;
     i := i + 1;
end;
if ok then
     write("Numarul ", nr, " este prim")
else 
     write("Numarul ", nr, " NU este prim");

Sau ne putem folosi de un loop repeat:

read(nr);
ok := true;
i := 2;
repeat
     if nr mod i = 0 then
          ok := false;
     i := i + 1;
until i = nr;
if ok then
     write("Numarul ", nr, " este prim")
else 
     write("Numarul ", nr, " NU este prim");

C’ya next time!

3 comentarii pentru Numere prime in Pascal

  • Cristi - 8 aprilie

    Nu trebuie sa mergi pana la n-1, poti merge pana la trunc(sqrt(x)), e mult mai eficient.



  • nadena - 28 ianuarie

    M-a ajutat!!!))))



  • denis18 - 11 noiembrie

    mersi , ma ajutat .. :)



Discuta articolul Numere prime in Pascal



Mozku Network

Ne gasesti si pe Facebook

Articole noi

Fisiere populare

  • Proiect Atestat Informatica Visual FoxPro (569)
  • Baza de date auto revizuita (254)
  • Twitter Patterns (214)
  • Baza de date auto (148)
  • Flash Newsletter (127)