Java 使用欧几里德算法找到两个数的最大公因数(G.C.D)和最小公倍数(L.C.M)

欧几里德算法 是一种高效的算法，可以帮助我们找到两个数的最大公因数和最小公倍数。本文中，我们将学习使用欧几里德算法编写一个Java程序来找到两个数的最大公因数和最小公倍数。

两个数的最大公因数

最大公因数（G.C.D），也被称为最大公约数，是能够完全整除给定两个数的最大公因数。现在让我们看一个示例，并计算一个数的最大公因数。

因数 - 在数学中，因数是可以整除给定数的数字。

例如 - 8可以被1、2、4、8整除。因此，1、2、4、8是8的因数。

示例

考虑数字8和16

8的因数是：1、2、4、8

16的因数是：1、2、4、8、16

能够整除8和16的公因数是1、2、4、8。其中最大的公因数是8。因此，8是8和16的最大公因数。

两个数的最小公倍数

最小公倍数（L.C.M），也被称为最小公倍数，是能够被给定两个数整除的最小数字，即最小的公倍数。

倍数 - 在数学中，倍数是可以被给定数整除的数字。

例如 - 8、16、24、32等都可以被8整除。所以8、16、24、32是8的倍数。

示例

考虑数字8和16

8的倍数是8、16、24、…

16的倍数是16、32、48、…

能够被8和16整除的公倍数是16、32、48等等。两个数字的最小公倍数是16。因此，16是8和16的最小公倍数。

现在，我们要使用欧几里德算法来实现一个程序，以在较短的时间内找到两个数的最小公倍数和最大公因数。

欧几里德算法的原理是：

“如果a>b，并且a、b是两个整数，那么a和b的最大公因数与b和a除以b的余数的最大公因数相同。”

欧几里德算法

• 让我们将a和b视为两个数字

• 如果 b=0 ，那么我们返回 a 作为两个数字的最大公约数

• 否则，我们将 a 替换为 b ，b替换为a、b的余数，并递归调用最大公约数函数

• 找到最大公约数后，我们可以找到 最小公倍数 (a, b) = (a*b) / 最大公约数

示例

第一步是将较大的数（36）除以较小的数（24）并找到余数。我们可以使用取模运算符（%）来实现这个。

36 % 24 = 12

余数是12。然后我们将较小的数（24）除以余数（12）并找到新的余数。

24 % 12 = 0

余数为0，这意味着我们找到了24和36的最大公约数。最大公约数是最后一个非零的余数，即12。

因此，24和36的最大公约数是12。我们可以通过检查12是否是24和36的公共因子，并且没有更大的数能够同时整除24和36来确认这一点。

最小公倍数 (24,36) = (24*36)/12 = 72。

24和36的最小公倍数是72。

步骤

• 初始化这两个数字。

• 编写一个递归方法来找到这些数字的最大公约数。

• 创建一个自定义类对象。

• 使用自定义类对象从主方法调用递归方法。然后使用最大公约数值来找到这些数字的最小公倍数。

示例

在这个示例中，我们初始化两个数字，然后创建一个GCD类的对象，并通过使用该GCD类的对象调用GCD方法，将这两个数字传递给方法并获取GCD的值并存储。然后，我们使用两个数字相乘并除以GCD的值来计算LCM。然后，我们打印两个数字的GCD和LCM。

//Java Program to find G.C.D and L.C.M of two numbers using Euclid’s Algorithm
import java.util.*;
class Gcd{
   public  int GCD(int number1, int number2) {
      if (number2 == 0) {
         return number1;
      }
      return GCD(number2, number1 % number2);
   }
}
public class Main {
   public static void main(String[] args) {
      int number_1 = 36;
      int number_2 = 24;
      Gcd gcdObject =  new Gcd();
      int gcd = gcdObject.GCD(number_1, number_2);
      System.out.println("G.C.D of "+" "+number_1+" & "+number_2 +" is: "+gcd);
      int lcm = (number_1 * number_2) / gcd;
      System.out.println("L.C.M of "+" "+number_1+" & "+number_2 +" is: "+lcm);
   }
}

输出

G.C.D of  36 & 24 is: 12
L.C.M of  36 & 24 is: 72

因此，在本文中我们使用Java编程计算了两个数字的最大公约数（G.C.D）和最小公倍数（L.C.M），采用了欧几里得算法。