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

Метод 1: алгоритм Евклида
Алгоритм Евклида — один из наиболее часто используемых методов расчета НОД. Он основан на том свойстве, что НОД двух чисел остается неизменным, когда меньшее число заменяется остатком от деления большего числа на меньшее.

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

Метод 2: факторизация простых чисел
Другой метод нахождения НОД – выполнить факторизацию простых чисел обоих чисел, а затем найти произведение общих простых множителей.

int gcd(int a, int b) {
    int smaller = (a < b) ? a : b;
    int gcd = 1;

    for (int i = 2; i <= smaller; i++) {
        if (a % i == 0 && b % i == 0) {
            gcd *= i;
            a /= i;
            b /= i;
            i--;
        }
    }

    return gcd;
}

Метод 3: алгоритм двоичного НОД (алгоритм Штейна)
Алгоритм двоичного НОД, также известный как алгоритм Стейна, — это эффективный метод вычисления НОД с использованием побитовых операций и целочисленного деления на 2.

int gcd(int a, int b) {
    if (a == 0)
        return b;
    if (b == 0)
        return a;

    int k;
    for (k = 0; ((a | b) & 1) == 0; ++k) {
        a >>= 1;
        b >>= 1;
    }

    while ((a & 1) == 0)
        a >>= 1;

    do {
        while ((b & 1) == 0)
            b >>= 1;

        if (a > b) {
            int temp = a;
            a = b;
            b = temp;
        }

        b = (b - a);
    } while (b != 0);

    return (a << k);
}

Метод 4: расширенный алгоритм Евклида
Расширенный алгоритм Евклида не только вычисляет НОД двух чисел, но также находит коэффициенты тождества Безу, которые представляют собой линейную комбинацию чисел, которая дает НОД.

int extendedGCD(int a, int b, int* x, int* y) {
    if (a == 0) {
        *x = 0;
        *y = 1;
        return b;
    }

    int x1, y1;
    int gcd = extendedGCD(b % a, a, &x1, &y1);

    *x = y1 - (b / a) * x1;
    *y = x1;

    return gcd;
}