«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. Алгоритм Штейна или алгоритм двоичного НОД

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

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

  1. gcd(0, 0) = 0, gcd(n1, 0) = n1, gcd(0, n2) = n2
  2. When n1 and n2 are both even integers, then gcd(n1, n2) = 2 * gcd(n1/2, n2/2), since 2 is the common divisor
  3. If n1 is even integer and n2 is odd integer, then gcd(n1, n2) = gcd(n1/2, n2), since 2 is not the common divisor and vice versa
  4. If n1 and n2 are both odd integers, and n1 >= n2, then gcd(n1, n2) = gcd((n1-n2)/2, n2) and vice versa

Мы повторяем шаги 2–4, пока n1 не станет равным n2 или n1 = 0. НОД равно (2n) * п2. Здесь 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 \u003e n2 равна O((log2n1)2), тогда как. когда n1 \u003c n2, это O((log2n2)2).

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

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

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