← Назад к математике

Алгоритм Евклида

Нахождение наибольшего общего делителя (НОД) двух чисел

🐍 Python
def gcd(a, b):
    if b > 0:
        return gcd(b, a % b)
    return a

a, b = map(int, input().split())
print(gcd(a, b))
⚙️ C++
#include <bits/stdc++.h>
using namespace std;

long long gcd(long long a, long long b) {
    if (b > 0)
        return gcd(b, a % b);
    return a;
}

int main() {
    long long a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    return 0;
}

Как работает алгоритм Евклида?

Алгоритм Евклида — это эффективный способ нахождения наибольшего общего делителя (НОД) двух чисел.

Основная идея

НОД(a, b) = НОД(b, a mod b)

Алгоритм основан на том, что если a и b делятся на d, то и их разность (a - b) также делится на d.

Пример работы

Найдём НОД(48, 18):

Ответ: 6

Временная сложность: O(log min(a, b)) — алгоритм работает очень быстро.

Формат ввода и вывода

Ввод: два целых числа a и b

Вывод: НОД(a, b)

Пример:

48 18

Вывод: 6

Попробовать онлайн

Результат появится здесь...