Java实现求最大公约数和最小公因数 |21xrx.com

Java实现求最大公约数和最小公因数

2023-06-14 11:43:03 深夜i -- --

Java 最大公约数最小公因数

在Java中，我们可以通过几种不同的方法来求取两个数的最大公约数和最小公因数。这些方法包括欧几里得算法、辗转相减法和质因数分解法等。下面将分别介绍这些算法的实现过程。

欧几里得算法是求最大公约数中最常用的一种算法。其实现原理是：两个数a和b的最大公约数等于b和a除以b的余数r的最大公约数。这个过程可以一直重复直至r为0，此时b就是两个数的最大公约数。代码实现如下：


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

辗转相减法的实现同样也比较简单，其原理是：两个数a和b的最大公约数等于a-b的差和小的那个数之间的最大公约数。这个过程同样可以一直重复，直到两个数相等为止，此时这个相等的数就是两个数的最大公约数。代码实现如下：


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

质因数分解法是求最小公倍数中最常用的一种算法。其实现原理是：两个数a和b的最小公倍数等于a和b中所有质因数的最高次幂的乘积。代码实现如下：


public static int lcm(int a, int b) {
  int gcd = gcd(a, b);
  return a * b / gcd;
}

综上所述，Java中实现求取最大公约数和最小公因数的方法有欧几里得算法、辗转相减法和质因数分解法。其中，欧几里得算法是求最大公约数中最常用的一种算法，而质因数分解法是求最小公倍数中最常用的一种算法。

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

下一篇: 如何用C语言将字体变大

评论区

()

相似文章