除了欧几里得之外最大的公约数算法

本文关键字：算法 几里 | 更新日期: 2023-09-27 18:35:41

我应该基本上生成3种不同的算法来查找GCD（a，b）。

其中一个是欧几里得的版本，所以我还需要两个。

实现是在 C# 中完成的。

建议？

除了欧几里得之外最大的公约数算法

（注意，在计算gcd(a,b)时，我们可以假设a <= b;如果不是这样，我们可以交换它们。

欧几里得算法无疑是计算 gcd 的最有效方法。但是，如果您需要另外两种（低效）方法来计算gcd(a,b)，则有很多：

  1. 从 a 开始并向下，测试每个数字以查看它是否将 a 和 b 除以。

  2. 素数分解a和b（获得素数的多集），并返回这些多集的交集的乘积。

  3. 找到a的所有除数，并测试它们是否从a开始除以b并向下除以。

  4. 通过测试b, 2*b, 3*b, ...中的哪一个可以被a整除来查找lcm(a,b)，并返回a*b/(lcm(a,b))。

1 和 4 可能最容易实现，因为它们不涉及因子分解。

注意一些边缘情况也很重要：gcd(0,x) = x适用于所有x > 0，而gcd(0,0)是未定义的。从技术上讲，我想gcd(a,b) = gcd(abs(a), abs(b))涵盖了输入可能是负数的情况。

以下是三种最常用的算法：

public static uint FindGCDModulus(uint value1, uint value2)
{
while(value1 != 0 && value2 != 0)
{
        if (value1 > value2)
        {
                value1 %= value2;
        }
        else
        {
                value2 %= value1;
        }
}
return Math.Max(value1, value2);
   }
public static uint FindGCDEuclid(uint value1, uint value2)
  {
while(value1 != 0 && value2 != 0)
{
        if (value1 > value2)
        {
                value1 -= value2;
        }
        else
        {
                value2 -= value1;
        }
}
return Math.Max(value1, value2);
}
 public static uint FindGCDStein(uint value1, uint value2)
 {
if (value1 == 0) return value2;
if (value2 == 0) return value1;
if (value1 == value2) return value1;
bool value1IsEven = (value1 & 1u) == 0;
bool value2IsEven = (value2 & 1u) == 0;
if (value1IsEven && value2IsEven)
{
        return FindGCDStein(value1 >> 1, value2 >> 1) << 1;
}
else if (value1IsEven && !value2IsEven)
{
        return FindGCDStein(value1 >> 1, value2);
}
else if (value2IsEven)
{
        return FindGCDStein(value1, value2 >> 1);
}
else if (value1 > value2)
{
        return FindGCDStein((value1 - value2) >> 1, value2);
}
else
{
        return FindGCDStein(value1, (value2 - value1) >> 1);
}
}

这是替代方案之一：

public static int gcd(int x, int y) {
    int result = 0;
    if (x<0) {
        x = -x;
    }
    if (y<0) {
        y = -y;
    }
    if (x == 0){
        result = y; 
    }
    if (y == 0){
        result = x; 
    }
    for (int i = 1; i < x+1; i++) {
        if ( x % i == 0) {
            if ( y % i == 0) {
                result = i;
            }
        }   
    } 
    return result; }

或多或少直接的方式是以下代码，它源自 Pick 定理：

int gcd(int a, int b)
{
     if( a < 0)
     {
         a = -a;
     }
     if( b < 0)
     {
         b = -b;
     }
     if( a == b)
     {
          return a;
     }
     //swap the values to make the upper bound in the next loop minimal
     if( a > b)
     {
        int swap = a;
        a = b;
        b = swap;
     }
     
     int temp=0;
     for(int i=1; i<=a; i++)
     {
          temp += math.floor(b*i/a);
     }
     return (a*b + b - a + temp)/2;
}
相关文章：