c# - 欧几里得以外的最大公约数算法

Question

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

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

实现是在 C# 中完成的。

建议？

Answer 1

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

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);
}
}

Answer 2

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

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

1. 从开始到a往下，测试每个数字，看它是否同时除以a和b。

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

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

4. lcm(a,b)通过测试找出哪个可b, 2*b, 3*b, ...被 整除a，然后返回a*b/(lcm(a,b))。

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

注意一些边缘情况也很重要：gcd(0,x) = x对于 all x > 0， whilegcd(0,0)是未定义的。从技术上讲，我认为gcd(a,b) = gcd(abs(a), abs(b))涵盖了输入可能为负的情况。

Answer 3

这是备选方案之一：

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; }

Answer 4

A more or less direct way is the following code, which is derived from Pick's theorem:

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;
}