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

1. Обзор

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

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

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

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

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 раз (эквивалентно меньшему числу), чтобы найти GCD.

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

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

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

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

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

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

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

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

gcd(0,, gcd(n1,, gcd(0,
Когда n1 и n2 являются четными целыми числами, то gcd(n1, * gcd(n1/2, n2/2) , так как 2 является общим делителем
Если n1 четное целое число и n2 нечетное целое число, то gcd(n 1,(n1/2, n2) , так как 2 не является общим делителем и наоборот
Если n1 и n2 являются нечетными целыми числами, и n1 , то gcd(n1, ((n1-n2)/2, n2) и наоборот

Мы повторяем шаги 2-4 до тех пор, пока n1 не станет равным n2 или n1 . GCD-это (2 ⁿ ) * 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((журнал 2 n1) 2 ) в то время как. когда n1 < n2, это O((журнал 2 n2) 2 ).

5. Заключение

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

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