21xrx.com
2025-03-23 13:53:58 Sunday
文章检索 我的文章 写文章
求最大公约数的Java算法
2023-06-14 15:51:45 深夜i     22     0
Java算法 最大公约数 欧几里得算法 Stein算法 移位操作

在计算机科学和数学领域，最大公约数（GCD）是两个或多个整数的最大公约数，也被称为最大公因数。Java是一种面向对象的编程语言，它提供了许多算法来计算最大公约数。本文将介绍使用Java实现求解最大公约数的算法，并且提供一些使用该算法的示例。

首先，我们来看一下最基本的算法：欧几里得算法，也称为辗转相除法。该算法基于两个定理：如果r是a除以b之后的余数，那么a和b的最大公约数等于b和r的最大公约数；如果r=0，则b是a和b的最大公约数。

然后，我们来看一下Java实现的欧几里得算法：

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

代码中的gcd方法接受两个整数作为参数，并返回它们的最大公约数。如果b等于0，则返回a，否则递归地计算b和a除以b之后的余数的最大公约数。

接下来，让我们看看如何使用Java实现更高效的算法，例如： Stein算法。该算法基于一个定理：如果a和b都是偶数，则gcd(a,b) = 2 × gcd(a/2, b/2)； 如果a是偶数且b是奇数，则gcd(a,b)=gcd(a/2,b)；如果a是奇数且b是偶数，则gcd(a,b)=gcd(a,b/2)；如果a和b都是奇数，则使用辗转相减法计算gcd(a-b,b)。该算法有一个优点，即可以处理大数，因为它可以在其中一个数变成0之前不断进行移位和减法。

以下是Java实现的Stein算法：

public int gcd(int a, int b) {
  if (a == 0)
    return b;
  
  if (b == 0)
    return a;
  
  int p = 0;
  while (((a & 1) == 0) && ((b & 1) == 0)) {
    a >>= 1;
    b >>= 1;
    ++p;
  }
  while ((a & 1) == 0)
    a >>= 1;
  
  while (b != 0) {
    while ((b & 1) == 0)
      b >>= 1;
    
    if (a > b)
      int temp = a;
      a = b;
      b = temp;
    
    b = b - a;
  }
  return a << p;
}

该方法从分解出的最小因素2开始，不断进行移位和减法，最终返回最大公约数。

  
  

评论区