21xrx.com
2025-03-25 09:28:42 Tuesday
文章检索 我的文章 写文章
Java实现最小公倍数算法
2023-06-13 22:04:11 深夜i     --     --
Java 最小公倍数 辗转相除法 枚举法

最小公倍数（LCM）是指多个整数中同时为它们的倍数时所需要的最小正整数，也称为最小公倍数。在Java编程中，可以通过一些算法来求取最小公倍数。本文将介绍两种常用的Java实现最小公倍数算法的方式。

1. 辗转相除法

辗转相除法，又称为欧几里得算法，是求最大公约数的常见算法之一。由于最小公倍数与最大公约数有以下关系：lcm(a, b) = a * b / gcd(a, b)，因此辗转相除法也可以用来求最小公倍数。

下面是Java实现辗转相除法的代码案例：

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

2. 枚举法

枚举法是一种暴力解法，它通过枚举每个数的倍数来求最小公倍数。具体实现过程是：首先找到这几个数中的最大值max，然后从max开始依次枚举max的倍数，直到找到能够同时被这几个数整除的最小数。

以下是Java实现枚举法的代码案例：

public static int lcm(int a, int b) {
  int max = Math.max(a, b);
  int lcm = 0;
  while(true) {
    lcm = max;
    if(lcm % a == 0 && lcm % b == 0)
      break;
    
    max++;
  }
  return lcm;
}

通过以上两种算法的实现，我们可以在Java编程中方便地求取最小公倍数。需要注意的是，对于比较大的数，枚举法的效率可能会比较低，因此建议选择辗转相除法来求解。

  
  

评论区