6161619792

Algorytm Euklidesa do wyznaczania gcd(a, b):

Założenie:

a i b są całkowitymi liczbami nieujemnymi, ponadto a >b. Pseudokod algorytmu: w bile (b źO) do

i

r := a mod b; a: = b; b : = r;

}

return (a)

Przykład:

Obliczenie gcd(4864, 3458):

krok 1		a = 4864	b = 3458	r = 1406
krok		a =3458	b = 1406	r = 646
krok 3		a = 1406	b = 646	r = 114
krok		a = 646	b = 114	r =76
krok		a = 114	b = 76	r = 38
krok 6		a = 76	b =38	r = 0
(krok 7):		a =38	b = 0 => gcd (4864, 3458) = 38

Algorytm Euklidesa w wersji rekurencyjnej:

Euclid(a, b)

{

if(b = 0) then return (a); else return Euclid(b, a mod b); _}_