Java实现辗转相除法 |21xrx.com

Java实现辗转相除法

2023-06-15 10:45:40 深夜i -- --

辗转相除法欧几里得算法最大公约数

辗转相除法，又称欧几里得算法，是求两个正整数最大公约数的算法。该算法基于一个定理：两个数的最大公约数等于其中较小的那个数和两数的差的最大公约数。例如：252和105的最大公约数是21（252=21×12，105=21×5），因为252−105×2=42，而42和105的最大公约数是21，于是可反复调用这个算法求出最大公约数。

下面是Java实现辗转相除法的代码：


public static int gcd(int a, int b) {
  if (b == 0)
    return a;
   else {
    return gcd(b, a % b);
  }
}

在上面的代码中，gcd方法采用了递归的方法。如果b等于0，那么最大公约数就是a。否则，计算a模b的结果，并将结果和b一起传递给递归的gcd方法。

下面是一个使用辗转相除法求两个数的最大公约数的例子：


public static void main(String[] args) {
  int a = 252;
  int b = 105;
  int result = gcd(a, b);
  System.out.println("最大公约数是：" + result);
}

这个例子输出的结果是：最大公约数是：21。

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

下一篇: 如何使用Java实现文本复制

评论区

()

相似文章