Нахождение НОД и НОК.

Задача:

Нахождение НОД и НОК двух чисел по алгоритму Евклида.

Описание:

Алгоритм Евклида:

a = b₁x₁ + r₁
b₁ = r₁x₂ + r₂
b₂ = r₂x₃ + r₃
...
b_n-1 = r_n-2x_n-1 + r_n-1
b_n = r_n-1x_n + 0

r_n-1 - НОД(a,b₁)

Код:


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.