Greatest common divisor/ru

From Free Pascal wiki

English (en) suomi (fi) français (fr) русский (ru)

Наибольшим общим делителем (НОД) двух целых чисел является наибольшее целое число, на которое делятся оба данных числа. Для чисел 121 и 143 наибольшим общим делителем является число 11.

Существует множество методов вычисления НОД. Например, алгоритм Евклида, основанный на делении:

Функция greatestCommonDivisor

function greatestCommonDivisor(a, b: Int64): Int64;
var
  temp: Int64;
begin
  while b <> 0 do
  begin
    temp := b;
    b := a mod b;
    a := temp
  end;
  result := a
end;

// алгоритм, основанный на вычитании
function greatestCommonDivisor_euclidsSubtractionMethod(a, b: Int64): Int64;
begin
  // работает только с положительными целыми числами
  if (a < 0) then a := -a;
  if (b < 0) then b := -b;
  // без входа в цикл, так как вычитание нуля не приведет к выходу из цикла
  if (a = 0) then exit(b);
  if (b = 0) then exit(a);
  while not (a = b) do
  begin
    if (a > b) then
     a := a - b
    else
     b := b - a;
  end;
  result := a;
end;

См. также

Внешние ссылки