Задачи «А»: Ввести с клавиатуры два натуральных числа и найти их НОД с помощью алгоритма Евклида Пример:Введите два числа: 21 14нод(21,14)-7

Задача: найти НОД двух натуральных чисел 21 и 14 с помощью алгоритма Евклида.

Пошаговое решение:

1. Пусть a = 21, b = 14. Убедимся, что a ≥ b.
2. Найдем остаток r от деления a на b: 21 = 14 × 1 + 7. Здесь r = 7.
3. Переход к следующему шагу: возьмём пары (a, b) = (14, 7).
4. Найдем остаток: 14 = 7 × 2 + 0. Здесь r = 0.
5. Когда остаток стал 0, НОД равен последнему ненулевому делителю, здесь это 7.

Ответ: НОД(21, 14) = 7.

Пояснение:

• В алгоритме Евклида используется свойство gcd(a, b) = gcd(b, a mod b). Каждый шаг уменьшает одно из чисел, пока остаток не станет нулём.
• Для любых чисел слагается, что НОД не меняется при замене пары (a, b) на (b, a mod b); продолжая, в конце получаем наибольший общий делитель.
• Временная сложность алгоритма пропорциональна O(log(min(a, b))).