Greatest common divisor/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;

См. также

• Наименьшее общее кратное
• Оператор mod
• mpz_gcd в GMP (библиотека высокой точности GNU)

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

• Пример рекурсивного алгоритма

From the Free Pascal wiki, page "Greatest common divisor/ru", as it stood on 2018-02-13 after a change by Useroflazarus, out of the wiki's dump of 2024-05-26. Copyright stays with the author who wrote it, according to the old wiki's Licensing page. If you have concerns about this material, message the admin.