使用欧几里得算法查找两个数字的最大公约数和最小公倍数的 Java 程序

---

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

两个数字的最大公约数

最大公约数（GCD），也称为最大公因数，是能够精确地整除两个给定数字的最高公因数。现在让我们来看一个例子，并计算两个数字的最大公约数。

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

例如 - 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 的最大公约数。

两个数字的最小公倍数

最小公倍数（LCM），也称为最小公倍数，是可以被两个给定数字整除的最小数字，即最小的公倍数。

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

例如 - 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 的余数，然后递归调用 GCD 函数。

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

示例

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

36 % 24 = 12

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

24 % 12 = 0

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

因此，24 和 36 的最大公约数是 12。我们可以通过检查 12 是否是 24 和 36 的公约数，以及是否有更大的数字可以均匀地整除 24 和 36 来确认这一点。

LCM(24,36) = (24*36)/12 = 72。

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

算法

• 初始化两个数字。

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

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

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

示例

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

//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 编程中的欧几里得算法计算了两个数字的最大公约数和最小公倍数。