Нахождение наибольшего общего делителя в Java

1. Обзор

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

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

2. Грубая сила

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

int gcdByBruteForce(int n1, int n2) {
    int gcd = 1;
    for (int i = 1; i <= n1 && i <= n2; i++) {
        if (n1 % i == 0 && n2 % i == 0) {
            gcd = i;
        }
    }
    return gcd;
}

Как мы видим, сложность приведенной выше реализации составляет O(min(n1, n2)) потому что нам нужно пройти цикл n раз (эквивалентно меньшему числу), чтобы найти НОД.

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

Во-вторых, мы можем использовать алгоритм Евклида, чтобы найти НОД. Алгоритм Евклида не только эффективен, но и прост для понимания и легко реализуем с помощью рекурсии в Java.

Метод Евклида основан на двух важных теоремах:

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

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

int gcdByEuclidsAlgorithm(int n1, int n2) {
    if (n2 == 0) {
        return n1;
    }
    return gcdByEuclidsAlgorithm(n2, n1 % n2);
}

Также обратите внимание, как мы используем n2 в позиции n1 и используем остаток в позиции n2 в рекурсивном шаге алгоритма .

Кроме того, сложность алгоритма Евклида составляет O(Log min(n1, n2)) , что лучше по сравнению с методом грубой силы, который мы видели ранее.

4. Алгоритм Штейна или бинарный алгоритм GCD

Наконец, мы можем использовать алгоритм Штейна, также известный как алгоритм бинарного НОД , чтобы найти НОД двух неотрицательных целых чисел. Этот алгоритм использует простые арифметические операции, такие как арифметические сдвиги, сравнение и вычитание.

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

1. НОД(0, 0) = 0, НОД(n1, 0) = n1, НОД(0, n2) = n2
2. Когда n1 и n2 оба являются четными целыми числами, тогда gcd(n1, n2) = 2 * gcd(n1/2, n2/2) , так как 2 является общим делителем
3. Если n1 — четное целое число, а n2 — нечетное целое число, то gcd(n1, n2) = gcd(n1/2, n2) , поскольку 2 не является общим делителем, и наоборот
4. Если n1 и n2 оба являются нечетными целыми числами и n1 >= n2 , то gcd(n1, n2) = gcd((n1-n2)/2, n2) и наоборот

Мы повторяем шаги 2-4, пока n1 не станет равным n2 или n1 = 0 . НОД равен (2 n ) * n2 . Здесь n — это количество раз, когда 2 встречается в числах n1 и n2 при выполнении шага 2:

int gcdBySteinsAlgorithm(int n1, int n2) {
    if (n1 == 0) {
        return n2;
    }

    if (n2 == 0) {
        return n1;
    }

    int n;
    for (n = 0; ((n1 | n2) & 1) == 0; n++) {
        n1 >>= 1;
        n2 >>= 1;
    }

    while ((n1 & 1) == 0) {
        n1 >>= 1;
    }

    do {
        while ((n2 & 1) == 0) {
            n2 >>= 1;
        }

        if (n1 > n2) {
            int temp = n1;
            n1 = n2;
            n2 = temp;
        }
        n2 = (n2 - n1);
    } while (n2 != 0);
    return n1 << n;
}

Мы видим, что мы используем арифметические операции сдвига, чтобы разделить или умножить на 2. Далее, мы используем вычитание, чтобы уменьшить заданные числа.

Сложность алгоритма Штейна при n1 > n2 равна O((log 2 n1) 2 ) , тогда как. когда n1 < n2, это O((log 2 n2) 2 ).

5. Вывод

В этом уроке мы рассмотрели различные методы вычисления НОД двух чисел. Мы также реализовали их на Java и быстро оценили их сложность.

Как всегда, полный исходный код наших примеров здесь, как всегда, на GitHub .