Finding Greatest Common Divisor in Java – 在Java中寻找最大公除数

最后修改: 2019年 8月 11日

中文/混合/英文(键盘快捷键：t)

1. Overview

1.概述

In mathematics, the GCD of two integers, which are non-zero, is the largest positive integer that divides each of the integers evenly.

在数学中，两个非零的整数的GCD是最大的正整数，它能平均地除以每个整数。。

In this tutorial, we’ll look at three approaches to find the Greatest Common Divisor (GCD) of two integers. Further, we’ll look at their implementation in Java.

在本教程中，我们将研究三种寻找两个整数的最大公因子（GCD）的方法。此外，我们还将看看它们在Java中的实现。

2. Brute Force

2.蛮力

For our first approach, we iterate from 1 to the smallest number given and check whether the given integers are divisible by the index. The largest index which divides the given numbers is the GCD of the given numbers:

对于我们的第一种方法，我们从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;
}

As we can see, the complexity of the above implementation is O(min(n1, n2)) because we need to iterate over the loop for n times (equivalent to the smaller number) to find the GCD.

我们可以看到，上述实现的复杂性是O(min(n1, n2))，因为我们需要在循环中迭代n次（相当于小数）来找到GCD。

3. Euclid’s Algorithm

3.欧几里德的算法

Second, we can use Euclid’s algorithm to find the GCD. Euclid’s algorithm is not only efficient but also easy to understand and easy to implement using recursion in Java.

其次，我们可以使用欧几里德算法来寻找GCD。欧几里德算法不仅效率高，而且易于理解，易于在Java中使用递归来实现。

Euclid’s method depends on two important theorems:

欧几里德的方法取决于两个重要的定理。

  • First, if we subtract the smaller number from the larger number, the GCD doesn’t change – therefore, if we keep on subtracting the number we finally end up with their GCD
  • Second, when the smaller number exactly divides the larger number, the smaller number is the GCD of the two given numbers.

Note in our implementation that we’ll use modulo instead of subtraction since it’s basically many subtractions at a time:

注意在我们的实现中，我们将使用modulo而不是减法，因为它基本上是一次做很多减法。

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

Also, note how we use n2 in n1‘s position and use the remainder in n2’s position in the recursive step of the algorithm.

另外，注意我们如何在n1的位置使用n2，并在算法的递归步骤中在n2的位置使用余数。

Further, the complexity of Euclid’s algorithm is O(Log min(n1, n2)) which is better as compared to the Brute Force method we saw before.

此外，欧几里德算法的complexity是O(Log min(n1, n2))，与我们之前看到的Brute Force方法相比更好。

4. Stein’s Algorithm or Binary GCD Algorithm

4.斯坦因算法或二进制GCD算法

Finally, we can use Stein’s algorithm, also known as the Binary GCD algorithm, to find the GCD of two non-negative integers. This algorithm uses simple arithmetic operations like arithmetic shifts, comparison, and subtraction.

最后，我们可以使用斯坦因算法，也被称为二进制GCD算法，来寻找两个非负整数的GCD。这个算法使用简单的算术操作，如算术移位、比较和减法。

Stein’s algorithm repeatedly applies the following basic identities related to GCDs to find GCD of two non-negative integers:

斯坦因算法反复应用以下与GCD有关的基本特性来寻找两个非负整数的GCD。

  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

We repeat steps 2-4 until n1 equals n2, or n1 = 0. The GCD is (2n) * n2. Here, n is the number of times 2 is found common in n1 and n2 while performing step 2:

我们重复步骤2-4，直到n1等于n2，或者n1=0。GCD是（2n）*n2。这里，n是在执行步骤2时发现2在n1和n2中共有的次数。

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;
}

We can see that we use arithmetic shift operations in order to divide or multiply by 2. Further, we use subtraction in order to reduce the given numbers.

我们可以看到，我们使用算术移位操作来除以或乘以2，此外，我们使用减法来减少给定的数字。

The complexity of Stein’s algorithm when n1 > n2 is O((log2n1)2) whereas. when n1 < n2, it is O((log2n2)2).

当n1 > n2时，斯坦因算法的复杂性是O((log2n1)2)n1 < n2时，它是O((log2n2)2).。

5. Conclusion

5.总结

In this tutorial, we looked at various methods for calculating the GCD of two numbers. We also implemented these in Java and had a quick look at their complexity.

在本教程中，我们研究了计算两个数字的GCD的各种方法。我们还用Java实现了这些方法，并快速了解了其复杂性。

As always, the full source code of our examples here is, as always, over on GitHub.

像往常一样，我们这里的例子的完整源代码一如既往地在GitHub上。