Java中求最大公约数和最小公倍数的方法详解 |21xrx.com

Java中求最大公约数和最小公倍数的方法详解

2023-06-15 10:36:02 深夜i -- --

Java开发最大公约数最小公倍数

在Java开发中，有时需要对数据进行一些计算处理，比如求最大公约数和最小公倍数。那么Java中应该怎样求解呢？本文将从两种方式进行详细讲解。

方式一：暴力枚举法

暴力枚举法是一种简单易懂的算法，在Java中可以非常方便地实现。它的原理是：对于两个数a和b，我们可以从它们中较小的数开始，依次向下枚举，找到它们的最大公约数。同样地，我们也可以从它们中较大的数开始，依次向上枚举，找到它们的最小公倍数。

代码实现：


public static int getGcd(int a, int b) {
  int gcd = 1;
  for (int i = 1; i <= Math.min(a, b); i++) {
    if (a % i == 0 && b % i == 0)
      gcd = i;
    
  }
  return gcd;
}
public static int getLcm(int a, int b) {
  int lcm = Math.max(a, b);
  while (true) {
    if (lcm % a == 0 && lcm % b == 0)
      break;
    
    lcm++;
  }
  return lcm;
}

方式二：辗转相除法

辗转相除法，又称欧几里得算法，是一种更加高效的算法。它的原理是：对于两个数a和b，我们可以用b除以a的余数r代替原来的b，然后继续用原来的a除以r的余数，直到余数为0为止。最后的除数就是它们的最大公约数。同样地，我们也可以用它们的乘积除以最大公约数，得到它们的最小公倍数。

代码实现：


public static int getGcd(int a, int b) {
  return b == 0 ? a : getGcd(b, a % b);
}
public static int getLcm(int a, int b) {
  return a * b / getGcd(a, b);
}

总结：

可以看出，使用辗转相除法计算最大公约数和最小公倍数的代码要更加简洁和高效，而暴力枚举法则需要更多的循环判断，计算时间会较长。因此，在实际开发中，我们应该适当选择不同的方法，根据具体需求进行处理。

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

下一篇: 为什么C语言中do-while循环的条件是退出循环

评论区

()

相似文章