Greatest common divisor · Наибольший общий делитель
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · Эта страница требует современного браузера (с поддержкой SharedArrayBuffer). Пожалуйста, обновите Chrome, Edge, Firefox или Safari до последней версии.
English
Greatest common divisor
The GCD of two numbers is the largest integer that divides both. Euclid's algorithm is beautifully short: while b isn't 0, replace the pair (a, b) with (b, a % b). When b reaches 0, a is the answer.
Русский
Наибольший общий делитель
НОД двух чисел — это наибольшее целое число, которое делит оба. Алгоритм Евклида beautifully короток: пока b не равно 0, замените пару (a, b) на (b, a % b). Когда b достигнет 0, a будет ответом.
Complete int gcd(int a, int b) to return the greatest common divisor of a and b. Euclid's method: repeatedly replace (a, b) with (b, a % b) until b is 0. · Завершите int gcd(int a, int b) для нахождения наибольшего общего делителя a и b. Метод Евклида: многократно заменяйте (a, b) на (b, a % b), пока b не станет равным 0.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.