Java实现最大公约数算法及代码案例 |21xrx.com

Java实现最大公约数算法及代码案例

2023-06-14 22:28:52 深夜i -- --

Java 最大公约数算法

在数学中，最大公约数（GCD）是两个或多个整数的最大公因数。在计算机编程中，求最大公约数也是一个运用较多的算法。下面我们来讲解如何使用Java语言来实现求最大公约数。

方法一：使用暴力枚举法

这种解法是看两个整数是否能够整除，来判断它们的最大公约数。

代码实现如下：


public static int gcd(int num1, int num2) {
  int gcd = 1;
  for(int i = 1; i<=num1 && i<=num2; i++) {
    if(num1%i == 0 && num2%i == 0)
      gcd = i;
    
  }
  return gcd;
}

方法二：使用辗转相除法

又叫欧几里得算法，是通过辗转相除的方法来求两个整数的最大公约数的。

代码实现如下：


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

以上两种方法都可以求得两个整数的最大公约数，但是使用辗转相除法会更加高效。

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

下一篇: 「Java程序为何能够跨平台运行

评论区

()

相似文章