Java实现辗转相除法求最大公约数 |21xrx.com

Java实现辗转相除法求最大公约数

2023-06-16 13:41:42 深夜i -- --

Java 最大公约数辗转相除法

辗转相除法也称欧几里得算法，是一种求得两个正整数的最大公约数（GCD）的算法。它基于以下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。该算法可以递归地定义为：

gcd(a, b) = gcd(b, a mod b), 其中a mod b为a除以b的余数。

下面是用Java实现辗转相除法求最大公约数的代码：


public class GCD {
 public static int gcd(int a, int b) {
  if (b == 0)
   return a;
   else {
   return gcd(b, a % b);
  }
 }
 public static void main(String[] args) {
  int a = 15;
  int b = 25;
  System.out.println("gcd(" + a + ", " + b + ") = " + gcd(a, b));
 }
}

上述代码中，gcd()方法采用了递归的思路，在b等于0时返回a作为最大公约数，否则递归调用gcd()方法直到b等于0。

在本例中，a和b的值分别为15和25。通过调用gcd()方法求出它们的最大公约数，并将结果输出到控制台。

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

下一篇: Java实现Excel数据导入数据库

评论区

()

相似文章