Java 求最大公约数示例 |21xrx.com

2023-06-15 15:15:07 深夜i -- --

Java 最大公约数代码示例

Java 求最大公约数示例 |

在 Java 中求最大公约数可以使用两种方法：辗转相除法和更相减损术。下面分别介绍这两种方法，并给出代码示例。

1. 辗转相除法

辗转相除法也叫欧几里得算法，可以在不断用大数除以小数，得到余数再用小数除以余数的过程中逐渐缩小这两个数之间的差距，当余数为零时，除数即为最大公约数。具体实现如下：


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

其中 `a`、`b` 为待求最大公约数的两个数，如果 `b` 为零，则返回 `a`，否则递归调用 `gcd(b, a % b)` 求 `b` 和 `a % b` 的最大公约数。

2. 更相减损术

更相减损术可以在两个数差距较大的情况下更快地求出最大公约数，但是可能会出现死循环或递归次数过多的问题。具体实现如下：


public static int gcd(int a, int b){
  if (a == b)
    return a;
  else if (a > b)
    return gcd(a - b, b);
  else
    return gcd(a, b - a);
}

其中 `a`、`b` 为待求最大公约数的两个数，如果 `a` 等于 `b`，则返回 `a` 或 `b`，否则比较 `a` 和 `b` 的大小，将较大的数减去较小的数，递归调用 `gcd(a - b, b)` 或 `gcd(a, b - a)` 求差和较小的数的最大公约数。

以上就是 Java 求最大公约数的两种方法及示例代码，读者可以自行选择合适的方法进行实现。

关键词：Java、最大公约数、辗转相除法、更相减损术、代码示例

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

下一篇: Java期末考试完美解析：填空题及答案全解析！

()

相似文章