21xrx.com
2025-03-27 12:29:35 Thursday
文章检索 我的文章 写文章
Java实现辗转相除法求最大公约数
2023-06-15 13:26:04 深夜i     --     --
Java 辗转相除法 最大公约数

辗转相除法，又称欧几里得算法，是求两个数最大公约数的一种常见方法。在Java中，可以很方便地通过循环语句来实现这个算法。

下面是Java代码实现最大公约数：

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

代码解析：

首先判断a和b的大小关系，如果a小于b，则交换a和b的值。这是因为辗转相除法要求大数除以小数，而我们不知道用户输入的两个数哪个大哪个小。

接下来，判断b是否是a的约数，如果是，那么b就是最大公约数，直接返回b即可。

如果b不是a的约数，那么就可以用a除以b，得到余数r。此时问题就转化为求b和r的最大公约数。因为b和r的大小关系不确定，所以可以把问题再次递归调用gcd()函数，直到b是r的约数。

最后，如果r等于0，则说明a和b的最大公约数就是b。

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

public class GCD {
  public static void main(String[] args){
    int a = 15;
    int b = 35;
    int result = gcd(a, b);
    System.out.println("The greatest common divisor of "+ a +" and "+ b +" is "+result);
  }
  public static int gcd(int a, int b){
    if (a < b)
      int temp = a;
      a = b;
      b = temp;
    
    if (a % b == 0)
      return b;
     else {
      return gcd(b, a % b);
    }
  }
}

这段代码演示了如何计算15和35的最大公约数，并打印出了结果。你可以替换a和b的值，观察程序输出的结果。如果运行成功，则会输出类似下面的结果：

The greatest common divisor of 15 and 35 is 5

本文介绍了如何使用Java实现辗转相除法求最大公约数，核心算法是递归求解。只要理解了算法的原理，用Java实现就相对简单了。

  
  

评论区