НОД и НОК (Евклид)

DP.08 · Основы

Задача

Найти НОД и НОК двух целых чисел.

Алгоритм

НОД: пока b не ноль, заменяем пару (a,b) на (b, a mod b). НОК = a/НОД*b.

Исходный код

⇩ Скачать 08-algoritm-evklida.dpr

program AlgoritmEvklida;
{$mode delphi}{$apptype console}
function NOD(a, b: Int64): Int64;
var t: Int64;
begin
  while b <> 0 do begin t := b; b := a mod b; a := t; end;
  Result := a;
end;
var a, b, g: Int64;
begin
  Write('a = '); ReadLn(a);
  Write('b = '); ReadLn(b);
  g := NOD(a, b);
  WriteLn('НОД = ', g);
  if g <> 0 then WriteLn('НОК = ', (a div g) * b);
  ReadLn;
end.

Пояснения

Тип Int64 и порядок a div g * b защищают от промежуточного переполнения.