Java 如何求最大公因数？ |21xrx.com

Java 如何求最大公因数？

2023-06-11 16:16:18 深夜i -- --

Java 最大公因数辗转相除法

在 Java 中，我们可以通过辗转相除法来求两个数的最大公因数。首先，我们要知道，如果一个数 a 能整除另一个数 b，那么 a 就是 b 的约数。而两个数的最大公因数，就是它们的约数中最大的那个数。

使用辗转相除法求最大公因数的基本步骤如下：

1. 将输入的两个数 a 和 b 比较大小，如果 a < b，则交换它们的顺序，即让 a 为大数，b 为小数。

2. 用较大的数 a 除以较小的数 b，得到余数 r。

3. 如果 r 等于 0，则 b 即为最大公因数。

4. 如果 r 不等于 0，则让 a 等于 b，b 等于 r，然后回到第 2 步，继续执行。

下面是 Java 中实现辗转相除法求最大公因数的代码示例：


public static int getGreatestCommonDivisor(int a, int b) {
  int big = a > b ? a : b;
  int small = a < b ? a : b;
  if (big % small == 0)
    return small;
  
  return getGreatestCommonDivisor(big % small, small);
}

以上代码中，我们定义了一个 getGreatestCommonDivisor 方法，在方法中实现了辗转相除法求最大公因数的逻辑。在程序中，我们先找到两个数中较大的数和较小的数，然后通过循环递归，不断将较大的数对较小的数取模，最终得到最大公因数。

上一篇: idea打包java可执行jar包

下一篇: Java常用内置对象一览及其常见方法详解

评论区

()

相似文章