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

А теперь к настоящим алгоритмам, а не использованию уже написанных в стандартной библиотеке. Читаем условие задачи: Алгоритм Евклида - это, действительно, эффективный способ вычисления наибольшего общего делителя двух чисел. Но та версия, которую изучил Дима из условия задачи является неоптимальной. Давайте посмотрим на примере. Если даны два числа 1000000 и 12, то шаг 4 будет выполняться очень много раз (83333), после чего a будет равно 4, а b - 12 (затем, они, конечно, поменяются местами). На примере мы можем заметить, что 1000000 = 83333 * 12 + 4, или в общем виде a = k * b + r...

Данный калькулятор может найти наибольший общий делитель (НОД) и наименьшее общее кратное (НОК) по алгоритму Евклида вычитанием, либо делением и дать подробное решение https://matematika-club.Ru https://matematika-club...