Используя алгоритм Евклида, найдите наибольший общий делитель чисел:
437 и 133
735 и 1050
1848 и 375
805 и 1265

Продемонстрируем на третьем примере1848      375Находим разность:1848-375=1473Теперь получили числа:1473        375Находим разность1473-375=1098 и т.д:1098-375=723723-375=348375-348=27(ВНИМАНИЕ! Всегда от большего вычитаем меньшее - то есть нельзя вычитать 348-375 !)348-27=321321-27=294294-27=267267-27=240240-27=213213-27=186186-27=159159-27=132132-27=105105-27=7878-27=5151-27=2427-24=324-3=2121-3=1818-3=1515-3=1212-3=99-3=66-3=3Итак НОД=31848/3=616375/3=125Как видим, алгоритм Евклида довольно медленный.Позже получили расширенный алгоритм Евклида, где монотонное вычитание заменили делением. Вычисление НОД расширенным алгоритмом значительно быстрее