	Biologie	Chimie	Didactica	Fizica	Geografie	Informatica
	Istorie	Literatura	Matematica	Psihologie

Informatica

Index » educatie » Informatica
» Divizibilitate. Numere prime.

Divizibilitate. Numere prime.

Generarea divizorilor proprii unui numar

Acest algoritm consta in impartirea numarului n (numar pentru care cautam divizorii proprii) la toate numerele naturale incepand cu valoare 2 si pana la valoarea n/ Daca n se imparte fara rest la la o valoare dintre cele precizate anterior, atunci acea valoare este divisor propriu pentru numarul n. Algoritmul se poate optimiza reducand plaja valorilor posibile pana la radacina patrata a lui n, reducand astfel timpul de executie.

citeste n;

pentru i=2,n/2 executa

daca n mod i =0 atunci

scrie i

sfarsit

program divizori;

var n,i:integer;

begin

write('n=');

readln(n);

i:=2;

while i<= sqrt(n) do

begin

if n mod i = 0 then writeln(i,' este divizor');

i:=i+1;

end;

end.

Generarea divizorilor primi ai unui numar -

descompunerea unui numar in factori primi

Generarea divizorilor primi ai unui numar se bazeaza pe adevarul matematic care spune ca prin impartirea repetata a unui numar n la un divizor oarecare i, pana cand n (catul obtinut prin impartire) nu mai este divizibil cu i, numarul n nu va fi divizibil prin niciun multimplu al divizorului i.

1.Generarea divizorilor primi

citeste n;

i←2;

cat timp n<>1 executa

ok←0;

cat timp n mod i =0 executa

n←n div i;

ok←1;

sfarsit ;

daca ok=1 atunci

scrie i;

sfarsit

i←i+1;

sfarsit

program divizori_primi;

var n,i:integer;

ok:boolean;

begin

write('n=');

readln(n);

i:=2;

while n<>1 do

ok:=false;

begin

while n mod i =0 do

begin

n:=n div i;

ok:=true;

end;

if ok = true then writeln(i,' este divizor prim');

i:=i+1;

end;

readln;

end.

Descompunerea in factori primi

citeste n;

i←2;

cat timp n<>1 executa

f←0;

ok←0;

cat timp n mod i =0 executa

n←n div i;

f←f+1;

ok←1;

sfarsit ;

daca ok=1 atunci

scrie I , 'la puterea' , f;

sfarsit

i←i+1;

sfarsit

program factori_primi;

var n,I,f:integer;

ok:boolean;

begin

write('n=');

readln(n);

i:=2;

while n<>1 do

begin

f:=0; ok:=false;

while n mod i =0 do

begin

n:=n div i;

f:=f+1;

ok:=true;

end;

if ok = true then

writeln('factor prim ',i,' la puterea ',f);

i:=i+1;

ok:=false;

end;

readln;

end.

Numar prim

Un numar natural diferit de 1 este prim daca are numai doi divizori, pei cei improprii. In cazul in care numarul are un divizor propriu atunci el nu este prim. Un posibil algoritm care determina daca un numar este prim sau nu arata astfel:

citeste n;

ok←1;

pentru i←2,trunk(sqrt(n)) executa

daca n mod i =0 atunci

ok←0;

sfarsit

daca ok=1 atunci

scrie 'Este prim'

altfel

scrie 'Nu este prim'

sfarsit

program este_prim;