Алгоритм Евклида (наибольший общий делитель)

Помечено: ,

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 4 нед., 1 день назад.

  • Автор
    Сообщения
  • #5395
    @admin

    Согласно алгоритма Евклида для двух чисел:

    1. вычисления завершаются если числа равны — в этом случае наибольший общий делитель совпадает со значением этих чисел;
    2. если числа не равны — надо выбрать из них большее и заменить его разностью чисел.

    Также возможен вариант, где вычитание заменено делением:

    1. Делим большее число на меньшее с остатком
    2. Если остаток равен 0, то есть большее число делится на меньшее нацело, то меньшее число и есть НОД, мы переходим к концу. Иначе — заменяем большее число на этот самый остаток и производим операцию 1 снова.

Для ответа в этой теме необходимо авторизоваться.