Java实现辗转相除法求最小公倍数 |21xrx.com

Java实现辗转相除法求最小公倍数

2023-06-15 14:08:39 深夜i -- --

Java 辗转相除法最小公倍数

在数学中，辗转相除法是求取两个正整数的最大公约数的一种常见方法，而最小公倍数是求两个数的公倍数中最小的一个数。本篇文章将介绍如何使用Java来实现使用辗转相除法求最小公倍数。

首先，我们需要了解两个数的最小公倍数是它们的乘积除以它们的最大公约数，也就是lcm(a,b) = a*b / gcd(a,b)。

接下来，我们通过辗转相除法来求取两个数的最大公约数，具体实现过程如下：


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

我们通过不断的用较小的数去除较大的数，然后用较大的数对余数取模，直到余数为0为止，此时，较小的数即为最大公约数。

有了最大公约数，求最小公倍数就非常简单了，直接套公式即可。


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

最后，我们可以在main函数中调用lcm来实现求两个数的最小公倍数：


public static void main(String[] args) {
  int a = 12, b = 20;
  int result = lcm(a, b);
  System.out.printf("The lcm of %d and %d is %d.", a, b, result);
}

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

下一篇: 【教程】Java计数器源代码详解及应用实例

评论区

()

相似文章