寻找超过2个整数的GCD(最大公约数)？

Question

我已经有一个找到2个数字的GCD的函数.

function getGCDBetween($a, $b)
{
    while ($b != 0)
    {
        $m = $a % $b;
        $a = $b;
        $b = $m;
    }
    return $a;
}

但现在,我想扩展此功能以找到N点的GCD.有什么建议吗？

Answer 1

有一种更优雅的方式来做到这一点:

// Recursive function to compute gcd (euclidian method)
function gcd ($a, $b) {
    return $b ? gcd($b, $a % $b) : $a;
}
// Then reduce any list of integer
echo array_reduce(array(42, 56, 28), 'gcd'); // === 14

如果要使用浮点,请使用近似值:

function fgcd ($a, $b) {
    return $b > .01 ? fgcd($b, fmod($a, $b)) : $a; // using fmod
}
echo array_reduce(array(2.468, 3.7, 6.1699), 'fgcd'); // ~= 1.232

您可以在PHP 5.3中使用闭包:

$gcd = function ($a, $b) use (&$gcd) { return $b ? $gcd($b, $a % $b) : $a; };

Answer 2

不得不做一些挖掘,但这是我发现的.

三个数字的gcd可以计算为gcd(a,b,c)= gcd(gcd(a,b),c),或者通过应用交换性和相关性以某种不同的方式计算.这可以扩展到任意数量的数字.

您可以使用以下内容:

function multiGCD($nums)
{
    $gcd = getGCDBetween($nums[0], $nums[1]);

    for ($i = 2; $i < count($nums); $i++) { $gcd = getGCDBetween($gcd, $nums[$i]); }

    return $gcd;
}