Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел. Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД. Алгоритм Евклида делением Пример: Найти НОД для 30 и 18. 30 / 18 = 1 (остаток 12) 18 / 12 = 1 (остаток 6) 12 / 6 = 2 (остаток 0) Конец: НОД – это делитель 6...