作为一个程序员 |21xrx.com

2023-06-16 14:11:59 深夜i 14 0

作为一个程序员，我经常要处理各种各样的算法问题。其中一个非常常见的问题就是求两个数的最大公约数和最小公倍数。

在Java中，实现最大公约数其实非常简单。Java提供了两种方式来实现最大公约数，分别是欧几里得算法和辗转相减法。

欧几里得算法又叫辗转相除法，基本思想是用除数去除它所在的位置的数后，得到的余数再去除除数，直到余数为0为止。最后的除数就是两个数的最大公约数。

下面是欧几里得算法的Java代码实现：

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

辗转相减法又叫欧几里得减法，基本思想是用大数减去小数，然后用得到的差值再去减小数，直到两数相等为止。最后的数就是两个数的最大公约数。

下面是辗转相减法的Java代码实现：

public static int gcd2(int a, int b) {
  while (a != b) {
    if (a > b)
      a -= b;
     else
      b -= a;
    
  }
  return a;
}

需要注意的是，在实际应用中，欧几里得算法更常用，因为它的效率比辗转相减法更高。

最小公倍数可以用两个数的积除以它们的最大公约数来求得。下面是求最小公倍数的Java代码实现：

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

总的来说，Java实现最大公约数和最小公倍数非常简单，不管是欧几里得算法还是辗转相减法，都可以轻松地完成。对于程序员来说，学习并掌握这些算法是非常重要的，因为在实际工作中会经常用到它们。

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

下一篇: C++相对于C语言最根本的变化

相似文章