Алгоритм Евклида(НОД и НОК)

Алгори́тм Евкли́да — алгоритм для нахождения наибольшего общего делителя двух целых чисел.
Реализация:

Pascal:

function nod( a, b: longint): longint;
begin
while (a <> 0) and (b <> 0) do
if a >= b then
a:= a mod b
else
b:= b mod a;
nod:= a + b;
end;

В рекурсивном виде:

function nod(var a, b: longint): longint;
begin
if (a = 0) or (b = 0) then
if a = 0 then
nod:= b
else
nod:= a
else
if a >= b then
nod:= nod( a mod b, b)
else
nod:= nod( a, b mod a)
end;

C:

int gcd(int a, int b) {
while(b) b^=a^=b^=a%=b;
return a;
}

Та же функция в рекурсивном виде:

int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}

Программа нахождения НОД и НОК алгоритмом Евклида на языке Pascal:

program nodnok; var a,b:longint; function NOD(x,y:longint):longint; begin if x<>0 then NOD:= NOD(y mod x,x) else NOD:= y; end; function NOK(x,y:longint):longint; begin NOK:= (x div NOD(x,y)) * y; end; Begin Write('Введите a и b: '); Readln(a,b); Writeln('НОД ',a,' и ',b,' = ', NOD(a,b)); Writeln('НОК ',a,' и ',b,' = ', NOK(a,b)); Readln; End.