Greatest common divisor/ru
From Lazarus wiki
Jump to navigationJump to search
│
English (en) │
suomi (fi) │
français (fr) │
polski (pl) │
русский (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)