如何用欧几里得算法求GCF/GCD？

Question

我创建了一种方法，可以让我找到两个数字的 GCF/GCD，虽然我有一个有效的代码，但我不知道它是如何工作的，也不知道它为什么工作。我了解 Euclid 算法，但不确定以下代码段如何使用它。

private int gcd(int a, int b) 
  {
  if (b == 0) 
     return a; 
  else if(a ==0) 
     return b;
  else
     return gcd(b, a % b);

  }

我对它返回的内容特别困惑，因为为什么要返回两个值？ a % b 是做什么的？这个怎么用欧几里得算法？

Answer 1

1) a % b 是做什么的？
% 是 Java 中的模数或余数运算符。 % 运算符 returns 两个数字的余数。例如 8 % 3 是 2，因为 8 除以 3 的余数是 2。

2) 欧几里德算法是基于两个数的最大公约数不变的原理，如果用它与较小数的差代替较大的数。实际上，您的 gcd 函数使用了欧几里得算法的更高效版本。当除以两个数字中较小的一个时，此版本将两个数字中较大的一个替换为其余数（对于此版本，算法在达到零余数时停止）。 Gabriel Lamé 在 1844 年证明了这一点 (https://en.wikipedia.org/wiki/Euclidean_algorithm)

3) 你的 gcd 函数没有返回两个值，它是一个递归函数。递归函数是一个函数，它要么调用自身，要么处于函数调用的潜在循环中。对于您的 gcd 函数，它会一直重复，直到两个参数之一变为零并且 gcd 值为剩余参数。
您可以在此 link.
中了解有关递归函数的更多信息 http://pages.cs.wisc.edu/~calvin/cs110/RECURSION.html

Answer 2

"the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number."

(wikipedia - Euclidean algorithm)

所以，取模：
Modulo returns 两个整数之间整数除法的余数。整数除法是没有分数或浮点数的除法。让我们将整数除法表示为 m /\ n。

m /\ n = o;  
m % n = p;  
o * n + p = m;

例如，

29 /\ 3 = 9; (3 goes - whole - into 29 9 times)  
29 % 3 = 2; (the integer division of 29 into 3 has a remainder of 2)  
9 * 3 + 2 = 29; (9 goes into 29 3 times (and 3 goes into 29 9 times), with a remainder of 2)

注意如果m小于n（即m < n），那么n进入m0次（m /\ n = 0), 所以整数除法的余数将是 m (m % n = m, 因为 o * n + p = m 所以 (0*n) + p = 0 + p = p = m);

那么，该功能是如何工作的？让我们尝试使用它。

1 - gcd(m, n), m < n
因此，如果我们以小于 n 的 m 开始 gcd(m, n)，那么在下一次嵌套调用 gcd 时唯一发生的事情就是参数的顺序发生变化：gcd(n, m % n) = gcd(n, m);

2 - gcd(n, m), m < n
好的，现在第一个参数比第二个大。
根据欧几里得算法，我们想对两个数中较大的一个进行处理。我们想用它和较小数字之间的差异来替换它。我们可以做 m - n 很多次。但是 m % n 所做的与从 m 中减去 n 的次数完全相同 before 这样做会导致负数。做减法看起来像 (((m - n) - n) - n) - n) 等等。但是如果我们把它展开，我们会得到： m - (n * o)。因为o * n + p = m，我们可以看到m - (n * o) = p和p = m % n。因此，重复从较大中减去较小与对较大与较小进行模数相同。
在下一步中，第二个参数可能是 0（如果 n 是 m 的约数）。在这种情况下，函数 returns n。这是正确的，因为 n 是其自身的除数，而且正如我们所见，它也是 m.
的除数或者，第二个参数可能小于 n。这是因为 m 到 n 的整数除法的余数必须小于 n - 这是因为，如果除法的余数大于 n，然后 n 可以再放入 m 一次，但事实并非如此；这是一个荒谬的结果。假设 n 不为 0，则第二个参数（我们称之为 p）小于 n.
所以，我们现在调用 gcd(n, p)，其中 p < n。

3 - gcd(n, p), p < n
现在发生了什么？好吧，我们与上一段中的位置完全相同。现在我们只是重复该步骤，即我们将继续调用 gcd(a, b)，直到传入 gcd(a ,b) 的两个数字中较小的一个是两个数字中较大的一个的除数，（意思是 a % b = 0) 在这种情况下，您只需 return 两个数字中较小的那个。

Answer 3

鉴于你的问题有几个组成部分，我将讨论欧几里德经典算法向你提出的递归方法的演变。请注意，此处介绍的方法假定 a >= b

下面的方法很可能实现了您熟悉的算法，即从 a（较大的数字）中重复减去 b（较小的数字），直到它不再更大或等于 b。如果 a == 0，没有余数，则 GCD 为 b。否则，交换 a 和 b 的值并继续重复减法。

public int classic_gcd(int a, int b) {
    while (true) {
        while (a >= b)
            a = a - b;

        if (a == 0)
            return b;

        int c = b;
        b = a;
        a = c;
    }
}

由于内部while循环，本质上是计算a除以b的提醒，可以用取模运算符代替。这极大地提高了算法的收敛速度，用单个模运算代替了潜在的大量减法。考虑找到 12,288 和 6 的 GCD，这将导致超过 2,000 次减法。此改进显示在下面的修改方法中。

public int mod_gcd(int a, int b) {
    while (true) {
        int c = a % b;
        if (c == 0)
            return b;

        a = b;
        b = c;
    }
}

最后，修改后的算法可以表示为递归算法，即调用自身，如下：

public int recurse_gcd(int a, int b) {
   if (b == 0)
       return a;
   else
       return recurse_gcd(b, a % b);
}

这个方法完成的和以前一样。但是，该方法不是循环，而是调用自身（如果未检查也是无限循环）。值的交换是通过更改传递给方法的参数的顺序来完成的。

请注意，以上方法仅用于演示，不应在生产代码中使用。

如何用欧几里得算法求GCF/GCD？

How to use Euclid's algorithm to find GCF/GCD?

java

algorithm

math

greatest-common-divisor