Java如何实现求最大公约数？ |21xrx.com

2023-06-14 16:49:42 深夜i -- --

Java 最大公约数欧几里得算法辗转相除法循环迭代

在Java中，求最大公约数有多种实现方法。其中比较常用的是欧几里得算法（又称辗转相除法）和更相减损术。

欧几里得算法的实现代码如下：


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

这段代码通过递归调用求解最大公约数。当b等于0时，a即为最大公约数；否则将b和a对b取余得到的余数作为新的b，继续递归调用gcd方法，直到b为0。

更相减损术的实现代码如下：


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

这段代码也通过递归调用求解最大公约数。当a等于b时，a即为最大公约数；否则将a和b的差作为新的a，继续递归调用gcd方法，直到a等于b。

除了递归法外，还可以用循环迭代来实现求最大公约数。其中，最常用的是辗转相除法的迭代实现代码如下：


public static int gcd(int a, int b) {
  while (b != 0)
    int temp = b;
    b = a % b;
    a = temp;
  
  return a;
}

这段代码通过循环迭代方式实现辗转相除法。每次利用a除以b得到的余数，更新a和b的值，直到b等于0，此时a即为最大公约数。

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

下一篇: 手机JavaScript不可用：如何在手机浏览器上禁用JavaScript

()

相似文章