Napisz funkcję, która będzie wykorzystywała algorytm Euklidesa do znajdowania największego wspólnego dzielnika (NWD) dwóch liczb naturalnych.
Algorytm Euklidesa nie wymaga rozkładania liczb na czynniki pierwsze. Wykorzystywana jest zależność: NWD dwóch liczb (a, b) jest równy a gdy b=0, lub jest równy NWD(b, a mod b) gdy b>=1.
function nwd(m,n:word):word;
var r:word;
begin
while m>0 do
begin
r:=n mod m;
n:=m;
m:=r;
end;
nwd:=n;
end;
Powyżej jest zamieszczony kod funkcji algorytmu Euklidesa, teraz zobaczmy jak ją wywołać - czyli użycie w praktyce:
begin
writeln('Podaj m');
readln(m);
writeln('Podaj n');
readln(n);
writeln(nwd(m,n));
readln;
end.
Warto zobaczyć
Szukasz hostingu?
Jest dużo firm oferujących hosting, ale którą wybrać? Przedstawiamy zestawienie najciekawszych propozycji i ranking hostingów (Czerwiec 2023).