21xrx.com
2024-11-25 05:59:54 Monday
登录
文章检索 我的文章 写文章
Java中如何求最大公因数和最小公倍数
2023-06-17 21:37:22 深夜i     --     --
Java 最大公因数 最小公倍数 辗转相减法 辗转相除法

在Java编程中，我们经常需要求最大公因数和最小公倍数。最大公因数指的是两个或多个数公有的最大因子，最小公倍数则是两个或多个数的公共倍数中最小的一个。

Java提供了多种求最大公因数和最小公倍数的方法，下面介绍两种常见的方法。

1. 辗转相减法

辗转相减法是一种求最大公因数的简单方法，其基本思想是用两个数中较小的数不断去减较大的数，直到两个数相等为止，此数即为最大公因数。最小公倍数则是两个数的乘积除以最大公因数。

Java代码实现如下：

public static int gcd(int a, int b) {

  while (a != b) {

    if (a > b)

      a = a - b;

     else

      b = b - a;

  }

  return a;

}

public static int lcm(int a, int b) {

  return a * b / gcd(a, b);

}

2. 辗转相除法

辗转相除法又称欧几里得算法，是一种求最大公因数的高效方法。其基本思想是用较大的数除以较小的数，再用除数除以余数，不断重复这个过程，直到余数为0，此时除数即为最大公因数。最小公倍数则是两个数的乘积除以最大公因数。

Java代码实现如下：

public static int gcd(int a, int b) {

  if (b == 0)

    return a;

  return gcd(b, a % b);

}

public static int lcm(int a, int b) {

  return a * b / gcd(a, b);

}

以上两种方法都可以用来求最大公因数和最小公倍数，具体选哪种方法，可以根据实际情况进行选择。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复