21xrx.com
2025-03-25 09:28:57 Tuesday
文章检索 我的文章 写文章
Java实现最大公约数和最小公倍数的方法
2023-06-14 11:03:07 深夜i     --     --
Java 最大公因数 最小公倍数

在Java中，求最大公因数和最小公倍数是常见的数学操作。这两个数学概念是很多问题的基础，比如分数化简，约分，等等。因此，Java提供了多种方法来实现这些计算。

求最大公因数和最小公倍数的代码可以使用两种不同的方法来实现：辗转相减法和辗转相除法。

辗转相减法

辗转相减法是计算最大公因数的一种简单算法。基本思想是用两个数的差值来更新两个数，直到两个数相等，这个相等的数就是最大公因数。

下面是一个使用辗转相减法的Java代码：

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

使用同样的方法，我们可以得到一个计算最小公倍数的Java代码：

public static int getLCM(int a, int b) {
  return a * b / getGCD(a, b);
}

辗转相除法

辗转相除法是计算最大公因数和最小公倍数的一种另类算法。它的基本思想是我们使用两个数的余数来更新两个数，直到其中一个数为0为止，这个时候另一个数就是最大公因数。

下面是一个使用辗转相除法的Java代码：

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

同样，我们可以使用辗转相除算法来计算最小公倍数：

public static int getLCM(int a, int b) {
  return a * b / getGCD(a, b);
}
  
  

评论区