21xrx.com
2025-03-22 05:36:04 Saturday
文章检索 我的文章 写文章
Java实现辗转相除法求最大公约数和最小公倍数
2023-06-18 20:55:53 深夜i     10     0
Java 辗转相除法 最大公约数 最小公倍数

辗转相除法，又称欧几里得算法，是一种求最大公约数（GCD）的算法，它基于一个定理：两个整数的最大公约数，等于其中较小的数和两数的差的最大公约数。通过不断取两数的余数、然后将两数中较小的那个作为被除数，余数作为除数，以此类推，直到余数为0，此时的被除数即为最大公约数。

最小公倍数（LCM）则可以通过最大公约数和原始两数的乘积来计算。因为两数的乘积等于它们的最大公约数与最小公倍数的积，即LCM(a,b) * GCD(a,b) = a * b。

下面是Java代码实现辗转相除法求最大公约数和最小公倍数：

public class GCD {
  public static int getGCD(int a, int b) {
    if (b == 0)
      return a;
     else {
      return getGCD(b, a % b);
    }
  }
  public static int getLCM(int a, int b) {
    return (a * b) / getGCD(a, b);
  }
  public static void main(String[] args) {
    int a = 48;
    int b = 18;
    
    int gcd = getGCD(a, b);
    int lcm = getLCM(a, b);
    
    System.out.println("最大公约数：" + gcd);
    System.out.println("最小公倍数：" + lcm);
  }
}

在这个例子中，我们定义了一个GCD类，其中包含了两个静态方法getGCD和getLCM。getGCD方法用递归算法来计算最大公约数，getLCM方法则直接用最大公约数和原始两数乘积来计算最小公倍数。最后在main函数中，我们定义了两个整数a和b，并使用getGCD和getLCM方法来求出它们的最大公约数和最小公倍数。

  
  

评论区