21xrx.com
2025-04-09 18:03:35 Wednesday
文章检索 我的文章 写文章
Java实现求最大公约数和最小公倍数
2023-06-15 20:34:22 深夜i     15     0
Java 求最大公约数 求最小公倍数

在编程中，求最大公约数和最小公倍数是很常见的需求。本文将介绍如何用Java语言实现求最大公约数和最小公倍数的方法。

方法一：暴力枚举法

暴力枚举法是最简单的求最大公约数和最小公倍数的方法。具体实现如下：

public static int maxCommonDivisor(int num1, int num2) {
    int result = 1;
    for (int i = 1; i <= num1 && i <= num2; i++) {
      if (num1 % i == 0 && num2 % i == 0)
        result = i;
      
    }
    return result;
  }
  public static int minCommonMultiple(int num1, int num2) {
    int result = num1 * num2;
    for (int i = num1 * num2; i >= num1 && i >= num2; i--) {
      if (i % num1 == 0 && i % num2 == 0)
        result = i;
      
    }
    return result;
  }

方法二：辗转相除法

辗转相除法也是一种常见的求最大公约数的方法，具体实现如下：

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

方法三：更相减损术

更相减损术也是一种常见的求最大公约数的方法，具体实现如下：

public static int maxCommonDivisor(int num1, int num2) {
    int temp;
    if (num1 < num2)
      temp = num1;
      num1 = num2;
      num2 = temp;
    
    if (num1 == num2)
      return num1;
    
    int diff = num1 - num2;
    return maxCommonDivisor(diff, num2);
  }

综上所述，本文介绍了Java语言实现求最大公约数和最小公倍数的三种方法。其中，暴力枚举法简单易懂，辗转相除法计算效率高，更相减损术比辗转相除法更适用于大数求解。

  
  

评论区

请求出错了