如何计算最小公分母

Question

也许是因为我的英语，我找不到任何东西。我想找到几个数字的最小除法值。 在德语中，它被称为：http://de.wikipedia.org/wiki/Hauptnenner 我想知道如何在 .Net 中执行此操作，因为我不敢相信这个问题是新问题，并且除了像在纸上那样计算“2 个分隔符和 3 个分隔符”之外还没有找到解决方案。

如果能得到任何建议将很高兴。

问候

Answer 1

该网站已经告诉您如何做到这一点：找到所有分母集合的最小公倍数。您可以利用最小公倍数和最大公约数之间的关系（请参阅维基百科）并简单地使用欧几里德算法（也可在维基百科上找到）。

Schau nach, wie du den ggT（groessten gemeinsamen Teiler berechnest -> Euklids Algorithmus）。 Danach kannst du den Hauptnenner aus dem kgV der Nenner berechnen。

Answer 2

最小公分母通常称为最小公乘数 LCM。两个数字 a 和 b 的 LCM（表示为 L(a, b)）与这些数字的最大公约数 GCD(a, b) 之间存在关系：

LCM(a, b) = a * b / GCD(a, b)

GCD(a, b) 可以使用以下公式非常有效地计算 ： 欧几里得算法。

此外，三个数字的 LCM 计算可以简化为两个数字的 LCM：

LCM(a, b, c) = LCM(LCM(a, b), c),

从而再次简化为两个数字的 GCD 计算。现在，计算 N 个数字的 LCM 的过程应该很明显了。

Answer 3

Jiri 展示了 LCM 和 GCD 如何简化为计算两个数字的 GCD。杰夫的算法对于大量数据来说太慢了。下面是一个算法的草图，该算法是输入数字长度的多项式，将它们称为 X 和 Y：

• 设置结果 = 1
• 如果 X 和 Y 都是偶数，则 ，结果 *=2； X/=2； Y/=2；
• 如果一个是偶数，另一个是奇数，是偶数的一半（没有其他更新）
• 如果两者都是奇数，则从较大的值中减去较小的值并迭代（注意，这为我们提供了

多项式复杂度的偶数-奇数组合证明事实上，在每两次迭代中，我们至少将其中一个数字减少至少一半

Answer 4

我一直在寻找与此类似的东西并提出了这个解决方案。我发现的大多数解决方案都是针对两个数字的，而我的解决方案需要处理未知数量的数字。不管怎样，这就是我想出来的。它对我有用，也许对你也有用。

    public static int GetLCM(int[] values) {
        var retval = values[0];
        for (var i = 1; i < values.Length; i++) {
            retval = GCD(retval, values[i]);
        }
        return retval;
    }
    private static int GCD(int val1, int val2) {
        while (val1 != 0 && val2 != 0) {
            if (val1 > val2) 
                val1 %= val2;
            else 
                val2 %= val1;
        }
        return System.Math.Max(val1,val2);
    }