Введите два натуральных числа с помощью клавиатуры и сравните количество итераций для вычисления их

Название: Алгоритм Евклида для вычисления НОД

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

1. Проверяем остаток от деления первого числа на второе число.
2. Если остаток равен нулю, то второе число является НОД.
3. Если остаток не равен нулю, заменяем второе число на остаток и повторяем шаг 1.

Модифицированный алгоритм Евклида является оптимизацией обычного алгоритма:

1. Проверяем остаток от деления первого числа на второе число.
2. Если остаток равен нулю, то второе число является НОД.
3. Если остаток не равен нулю, выполняем следующие шаги:
- Вычисляем остаток от деления остатка на второе число.
- Заменяем второе число на полученный остаток.
- Повторяем шаги 1 и 2.

Демонстрация:

Допустим, у нас есть два числа: 1998 и 2. Мы хотим найти их НОД с помощью обычного и модифицированного алгоритмов Евклида.

Обычный алгоритм Евклида:

1998 % 2 = 0 (остаток), следовательно, НОД(1998, 2) = 2.

Модифицированный алгоритм Евклида:

1998 % 2 = 0 (остаток)
2 % 0 = 2 (остаток), следовательно, НОД(1998, 2) = 2.

Совет: Если остаток от деления равен нулю, то это значит, что второе число является делителем первого числа и является НОД. Если остаток не равен нулю, продолжайте делить числа, пока не достигнете остатка, равного нулю.

Дополнительное задание: Найдите НОД для чисел 924 и 748 с использованием обычного и модифицированного алгоритмов Евклида.