Greatest common divisor/ru: what changed

Revision 0 to 1. Removed lines have a minus sign; added lines have a plus sign.

Title: Greatest common divisor/ru

New		Line
1	+	Наибольшим общим делителем (НОД) двух целых чисел является наибольшее целое число, на которое делятся оба данных числа. Для чисел 121 и 143 наибольшим общим делителем является число 11.
2	+
3	+	Существует множество методов вычисления НОД. Например, алгоритм Евклида, основанный на делении:
4	+
5	+	## Функция greatestCommonDivisor
6	+
7	+	``` pascal
8	+	function greatestCommonDivisor(a, b: Int64): Int64;
9	+	var
10	+	temp: Int64;
11	+	begin
12	+	while b <> 0 do
13	+	begin
14	+	temp := b;
15	+	b := a mod b;
16	+	a := temp
17	+	end;
18	+	result := a
19	+	end;
20	+
21	+	// алгоритм, основанный на вычитании
22	+	function greatestCommonDivisor_euclidsSubtractionMethod(a, b: Int64): Int64;
23	+	begin
24	+	// работает только с положительными целыми числами
25	+	if (a < 0) then a := -a;
26	+	if (b < 0) then b := -b;
27	+	// без входа в цикл, так как вычитание нуля не приведет к выходу из цикла
28	+	if (a = 0) then exit(b);
29	+	if (b = 0) then exit(a);
30	+	while not (a = b) do
31	+	begin
32	+	if (a > b) then
33	+	a := a - b
34	+	else
35	+	b := b - a;
36	+	end;
37	+	result := a;
38	+	end;
39	+	```
40	+
41	+	## См. также
42	+
43	+	- [[Least common multiple/ru\|Наименьшее общее кратное]]
44	+	- [[Mod/ru\|Оператор mod]]
45	+	- mpz_gcd в [[gmp\|GMP]] (библиотека высокой точности GNU)
46	+
47	+	## Внешние ссылки
48	+
49	+	- [Пример рекурсивного алгоритма](https://rosettacode.org/wiki/Greatest_common_divisor#Pascal_.2F_Delphi_.2F_Free_Pascal)
50	+
51	+	---
52	+	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](/wiki-contact).
53	+	Category: Mathematics/ru

Back to history