Difference between revisions of "Greatest common divisor/ru"
From Free Pascal wiki
Jump to navigationJump to search (Created page with "{{Greatest common divisor}} Наибольшим общим делителем ('''НОД''') двух целых чисел является наибольшее целое...") |
|||
Line 44: | Line 44: | ||
== См. также == | == См. также == | ||
− | * [[Least common multiple/ru| | + | * [[Least common multiple/ru|Наименьшее общее кратное]] |
* [[Mod/ru|Оператор mod]] | * [[Mod/ru|Оператор mod]] | ||
* mpz_gcd в [[gmp|GMP]] (библиотека высокой точности GNU) | * mpz_gcd в [[gmp|GMP]] (библиотека высокой точности GNU) |
Latest revision as of 19:31, 13 February 2018
│
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)