Java中如何计算最大公约数（GCD）和最小公倍数（LCM） |21xrx.com

2023-06-14 20:27:33 深夜i -- --

Java 算法最大公约数最小公倍数

Java中如何计算最大公约数（GCD）和最小公倍数（LCM）

在数学中，最大公约数和最小公倍数是两个重要的概念。在Java中，有两种方式来计算它们：欧几里得算法和辗转相除法。

欧几里得算法（又称为辗转相减法）：该算法基于下面的原理：如果a>b，则a和b的最大公约数等于a-b和b的最大公约数；如果a


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

辗转相除法（又称为欧几里得除法）：该算法基于下面的原理：如果a>b，则a和b的最大公约数等于b和a%b的最大公约数；如果a


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

最小公倍数也可以使用两种方法来计算：先计算最大公约数，然后将原始数字相乘并除以最大公约数，或者使用以下公式直接计算：LCM(a,b) = a * b / gcd(a,b)。示例代码如下：


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

综上所述，虽然最大公约数和最小公倍数都涉及到相除操作，但计算它们使用的算法略有不同。

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

下一篇: 了解Java中的static关键字

()

相似文章