Найти наибольший общий делитель двух натуральных чисел

Формулировка. Даны два натуральных числа. Найти их наибольший общий делитель.

Примечание: наибольшим общим делителем (сокращенно пишут НОД) двух натуральных чисел m и n называется наибольший из их общих делителей. Обозначение: НОД(m, n).

Примечание 2: общим делителем двух натуральных чисел называется натуральное число, на которое натуральное число, которое является делителем обоих этих чисел.

Например, найдем НОД(12, 8):

Выпишем все делители числа 12: 1, 2, 3, 4, 6, 12;

Выпишем все делители числа 8: 1, 2, 4, 8;

Выпишем все общие делители чисел 12 и 8: 1, 2, 4. Из них наибольшее число – 4. Это и есть НОД чисел 12 и 8.

Решение. Конечно, при решении мы не будем выписывать делители и выбирать нужный. В принципе, ее можно было бы решить как задачу 15, начав цикл с наименьшего из двух заданных чисел (так как оно тоже может быть НОД, например, НОД(12, 4) = 4). Но мы воспользуемся так называемым алгоритмом Евклида нахождения НОД, который выведен с помощью математических методов. В самом простейшем случае для заданных чисел m и n он выглядит так:

1)          Если m неравно n, перейти к шагу 2, в противном случае вывести m и закончить алгоритм;

2)          Если m > n, заменить m на m – n, в противном случае заменить n на n – m;

3)          Перейти на шаг 1

Как видим, в шаге 2 большее из двух текущих чисел заменяется разностью большего и меньшего.

Приведем пример для чисел 12 и 8:

1. Так как 12 > 8, заменим 12 на 12 – 8 = 4;
2. Так как 8 > 4, заменим 8 на 8 – 4 = 4;
3. 4 = 4, конец.

Не проводя каких-либо рассуждений над алгоритмом и не доказывая его корректности, переведем его описание в более близкую для языка Pascal форму:

Алгоритм на естественном языке:

1)      Ввод m и n;

2)      Запуск цикла с предусловием m < > n. В цикле:

1. Если m > n, то переменной m присвоить m – n, иначе переменной n присвоить n – m;

3)      Вывод m:

Код:

1. program GreatestCommonDiv;
2. var
3. m, n: word;
4. begin
5. readln(m, n);
6. while m <> n do begin
7. if m > n then begin
8. m := m — n
9. end
10. else begin
11. n := n — m
12. end
13. end;
14. writeln(m)
15. end.