一个由多于2个整数组成的集合中的最大公约数

Question

一个由多于2个整数组成的集合中的最大公约数

18

在Stack Overflow上有许多关于如何找到两个值的最大公约数的问题。一个很好的答案展示了一个整洁的递归函数来完成这个任务。

但是，如何找到一组超过2个整数的最大公约数呢？我似乎找不到任何例子。

有人能否建议最有效的代码来实现此函数？

static int GCD(int[] IntegerSet)
{
    // what goes here?
}

- BG100

5

GCD像加号和乘号一样具有结合律和交换律，因此您可以按任意顺序连续对数字应用GCD。 - starblue

1

如果C#像许多函数式语言一样为列表提供“inject”或“reduce”方法，那么这将非常简单。 - Justin L.

12个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

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

- Chang · Answer 2

通过这种方式，您也可以使用数组传递多个值：

// pass all the values in array and call findGCD function
    int findGCD(int arr[], int n) 
    { 
        int gcd = arr[0]; 
        for (int i = 1; i < n; i++) {
            gcd = getGcd(arr[i], gcd); 
        }

        return gcd; 
    } 

// check for gcd
    int getGcd(int x, int y) 
    { 
        if (x == 0) 
            return y; 
        return gcd(y % x, x); 
    }