Алгоритм Евклида в КуМире: наибольший общий делитель

Пример уже в редакторе: нажмите F9 — обычное выполнение или F8 — по шагам. Программу можно менять и запускать снова.

Алгоритм Евклида: пока оба числа не ноль, большее заменяют остатком от деления на меньшее. Когда одно число стало нулём, другое — наибольший общий делитель.

Загружаю среду КуМир… Если ничего не происходит — включите JavaScript и обновите страницу.

КуМир онлайн на SilverTests — неофициальная онлайн-версия, не продукт НИИСИ РАН. Язык, сообщения и поведение — как в «Кумир-Стандарт» 2.1.

Алгоритм Евклида: НОД: разбор

Остатки уменьшаются очень быстро, поэтому алгоритм работает за несколько шагов даже для больших чисел.

На что смотреть при выполнении

на полях — новые значения a и b на каждом шаге;
попробуйте числа 1071 и 462.

Программа на КуМире

алг НОД
нач
. цел a, b
. вывод "Два натуральных числа: "
. ввод a, b
. нц пока a <> 0 и b <> 0
. . если a > b
. . . то a := mod(a, b)
. . . иначе b := mod(b, a)
. . все
. кц
. вывод "НОД = ", a + b, нс
кон

Программа уже в редакторе. Нажмите F9, чтобы выполнить её со значениями на полях, или F8 — по шагам. Код можно менять и запускать заново, а «Программа → Сохранить» скачает его файлом .kum.

КуМир онлайн: как пользоваться и частые вопросы

Примеры программ на КуМире

Робот (ОГЭ, задание 15)

Чертёжник

Черепаха

Основы языка

Другие инструменты SilverTests

ОГЭ по информатике Онлайн-компилятор Python по шагам Python-черепашка ЕГЭ по информатике Курсы