使用欧几里得算法查找两个数字的 G.C.D 和 L.C.M 的 Java 程序

javaobject oriented programmingprogramming更新于 2024/3/17 8:44:17

欧几里得算法是一种有效的算法,可帮助我们找到两个数字的 G.C.D 和 L.C.M。在本文中,我们将学习编写一个 Java 程序,使用欧几里得算法查找两个数字的 G.C.D 和 L.C.M。

两个数字的 G.C.D.

G.C.D,称为最大公约数,是可以精确划分两个给定数字的最大公约数。现在让我们看一个例子并计算两个数字的 G.C.D。

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

Ex - 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.两个数的最小公倍数

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 作为这两个数字的最大公倍数数字。

  • 否则,我们用 b 替换 a,用 a、b 的余数替换 b,然后递归调用 GCD 函数。

  • 找到 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 来确认这一点。

最小二乘法(24,36) = (24*36)/12 = 72。

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

算法

  • 初始化这两个数字。

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

  • 创建自定义类对象。

  • 使用自定义类对象从主方法调用递归方法。然后使用 G.C.D 值找到数字的 L.C.M。

示例

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

//Java 程序使用欧几里得算法查找两个数字的 G.C.D 和 L.C.M
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 编程中的 Eculid 算法计算了 tw m=numbers 的 G.C.D 和 L.C.M。


相关文章


有用资源