Java 求两个数的最小公倍数

 Java 常见例子

LCM 代表最小公倍数。两个数的最小公倍数是可以被两个数整除的最小数。

例如 - 20 和 25 的最小公倍数是 100，30 和 40 的最小公倍数是 120。

从数学上讲，两个数字（a和b）的最小公倍数可以表示为:

a x b = LCM(a, b) x GCD(a, b)

LCM(a, b) = (a x b) / GCD(a, b) 

方法一:使用For循环求两个数字的GCD和最小公倍数

在下面的示例中，for 循环用于将变量 i 从 0 迭代到较小的数字。如果两个数字都能被i整除，那么它会修改GCD并最终给出两个数字的GCD。然后使用两个数字的 GCD 来计算两个数字的 LCM。

public class MyClass {
  public static void main(String[] args) {
    int x = 20;
    int y = 25;
    int gcd = 1;
    int temp, lcm;

    if (x > y) {
      temp = x;
      x = y;
      y = temp;
    }

    for(int i = 1; i < (x+1); i++) {
      if (x%i == 0 && y%i == 0)
        gcd = i;
    }

    lcm = (x*y)/gcd;
    System.out.println("LCM of "+ x +" and "+ y +" is: "+ lcm);
  }
} 

上面的代码将给出以下输出:

LCM of 20 and 25 is: 100 

方法 2:使用 While 循环求两个数字的 GCD 和 LCM

在下面的示例中，较大的数字被替换为通过从较大的数字减去较小的数字计算得出的数字。继续该过程，直到两个数字相等，这将是两个数字的 GCD。然后使用两个数字的 GCD 来计算两个数字的 LCM。

public class MyClass {
  public static void main(String[] args) {
    int p, q, x, y, lcm;
    p = x = 20;
    q = y = 25;

    while (x != y) {
      if (x > y)
        x = x - y;
      else
        y = y - x;
    }

    lcm = (p*q)/x;
    System.out.println("LCM of "+ p +" and "+ q +" is: "+ lcm);
  }
} 

上面的代码将给出以下输出:

LCM of 20 and 25 is: 100 

方法三:使用递归函数求两个数字的 GCD 和 LCM

在下面的例子中，使用了递归函数，它使用欧几里德算法来找到两个数字的GCD，并进一步用于计算两个数字的LCM。

public class MyClass {
  static int gcd(int x, int y) {
    if (y == 0)
      return x;
    return gcd(y, x%y);  
  }
  
  public static void main(String[] args) {
    int x = 30;
    int y = 40;

    int lcm = (x*y)/gcd(x,y);    

    System.out.println("LCM of "+ x +" and "+ y +" is: "+ lcm);
  }
} 

上面的代码将给出以下输出:

LCM of 30 and 40 is: 120