1. Overview

1.概述

Given two integers, a and b, we say that they are relatively prime if the only factor that divides both is 1. Mutually prime or coprime are synonyms for relatively prime numbers.

给定两个整数，a和b，我们说它们是相对质数，如果两者的唯一除数是1。

In this quick tutorial, we’ll walk through a solution to this problem using Java.

在这个快速教程中，我们将通过使用Java来解决这个问题。

2. Greatest Common Factor Algorithm

2.最大公因数算法

As it turns out, if the greatest common divisor (gcd) of 2 numbers a and b is 1 (i.e. gcd(a, b) = 1) then a and b are relatively prime. As a result, determining whether two numbers are relatively prime consists simply of finding if the gcd is 1.

事实证明，如果两个数字a和b的最大公除数（gcd）是1（即gcd（a，b）=1），那么a和b是相对素数。因此，确定两个数字是否为相对素数，只需要找出gcd是否为1。

3. Euclidean Algorithm Implementation

3.欧几里得算法的实现

In this section, we’ll use the Euclidean algorithm to calculate the gcd of 2 numbers.

在本节中，我们将使用欧几里得算法来计算2个数字的gcd。

Before we show our implementation, let’s summarize the algorithm and look at a quick example of how to apply it for the sake of understanding.

在展示我们的实现之前，为了便于理解，我们先总结一下这个算法，并看一下如何应用这个算法的一个简单例子。

So, imagine we have two integers, a and b. In the iterative approach, we first divide a by b and get the remainder. Next, we assign a the value of b, and we assign b the remainder value. We repeat this process until b = 0. Finally, when we reach this point, we return the value of a as the gcd result, and if a = 1, we can say that a and b are relatively prime.

所以，设想我们有两个整数，a和b。在迭代法中，我们首先用a除以b，得到余数。接下来，我们给a分配b的值，然后给b分配余值。我们重复这个过程，直到b=0。最后，当我们达到这一点时，我们将a的值作为gcd的结果返回，如果a=1，我们可以说a和b是相对素数。

Let’s try it out on two integers, a = 81 and b = 35.

让我们在两个整数上试试，a=81和b=35。

In this case, the remainder of 81 and 35 (81 % 35) is 11. So, in the first iteration step, we end with a = 35 and b = 11. Consequently, we’ll do another iteration.

在这种情况下，81和35（81 % 35）的剩余部分是11。因此，在第一个迭代步骤中，我们以a=35和b=11结束。因此，我们要再做一次迭代。

The remainder of 35 divided by 11 is 2. As a result, we have now a = 11 (we swapped values) and b = 2. Let’s keep going.

35除以11的剩余部分是2。结果，我们现在有a=11（我们交换了数值）和b=2。让我们继续下去。

One more step will result in a = 2 and b = 1. Now, we’re getting close to the end.

再走一步就会出现a=2和b=1。现在，我们已经接近尾声了。

Lastly, after one more iteration, we’ll reach a = 1 and b = 0. The algorithm returns 1 and we can conclude that 81 and 35 are indeed relatively prime.

最后，再经过一次迭代，我们将达到a=1和b=0。该算法返回1，我们可以得出结论：81和35的确是相对素数。

3.1. Imperative Implementation

3.1.强制执行

First, let’s implement the imperative Java version of the Euclidean algorithm as described above:

首先，让我们来实现上述欧几里得算法的Java命令式版本。

int iterativeGCD(int a, int b) {
    int tmp;
    while (b != 0) {
        if (a < b) {
            tmp = a;
            a = b;
            b = tmp;
        }
        tmp = b;
        b = a % b;
        a = tmp;
    }
    return a;
}

As we can notice, in the case where a is less than b, we swap the values before continuing. The algorithm stops when b is 0.

我们可以注意到，在a小于b的情况下，我们在继续之前交换了数值。当b为0时，算法停止。

3.2. Recursive Implementation

3.2.递归实现

Next, let’s look at a recursive implementation. This is probably cleaner since it avoids explicit variable value swaps:

接下来，让我们看看一个递归实现。这可能更干净，因为它避免了显式变量值的交换。

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

4. Using BigInteger‘s Implementation

4.使用BigInteger的实现

But wait — isn’t the gcd algorithm already implemented in Java? Yes, it is! The BigInteger class provides a gcd method that implements the Euclidean algorithm for finding the greatest common divisor.

但是等等–gcd算法不是已经在Java中实现了吗？是的，它已经实现了!BigInteger类提供了一个gcd方法，实现了寻找最大公除数的欧几里得算法。

Using this method, we can more easily draft the relatively prime algorithm as:

使用这种方法，我们可以更容易地起草相对素数算法为。

boolean bigIntegerRelativelyPrime(int a, int b) {
    return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).equals(BigInteger.ONE);
}

5. Conclusion

5.总结

In this quick tutorial, we’ve presented a solution to the problem of finding if two numbers are relatively prime using three implementations of the gcd algorithm.

在这个快速教程中，我们介绍了使用gcd算法的三种实现来寻找两个数字是否为相对素数的问题的解决方案。

And, as always, the sample code is available over on GitHub.

而且，像往常一样，样本代码可以在GitHub上找到。