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

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

Примечание: наибольшим общим делителем (сокращенно пишут НОД) двух натуральных чисел 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.

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

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

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

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

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

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

a. Так как 12 > 8, заменим 12 на 12 – 8 = 4;

b. Так как 8 > 4, заменим 8 на 8 – 4 = 4;

c. 4 = 4, конец.

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

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

1) Ввод m и n;

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

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

3) Вывод m:

Код: