这里是一个优雅的递归解决方案
<?php
function gcd($a,$b) {
return ($a % $b) ? gcd($b,$a % $b) : $b;
}
?>
(PHP 4 >= 4.0.4, PHP 5, PHP 7, PHP 8)
gmp_gcd — 计算 GCD
计算 num1 和 num2 的最大公约数。即使其中一个或两个输入操作数为负数，结果也始终为正数。
一个正 GMP 数，可以整除 num1 和 num2。
范例 #1 gmp_gcd() 范例
<?php
$gcd = gmp_gcd("12", "21");
echo gmp_strval($gcd) . "\n";
?>上面的例子将输出
3
这里是一个优雅的递归解决方案
<?php
function gcd($a,$b) {
return ($a % $b) ? gcd($b,$a % $b) : $b;
}
?>之前的函数在 php 5.2.4 下只返回 1，但以下似乎有效 (m>0,n>0)
function gcd($m,$n)
{
$_m=$m;$r=1;
if($m<$n){$t=$m;$m=$n;$n=$t;}
while($r)
{
$r=(floor($m/$n)*$n)-$m;
$_n=$n;$n=$r;$m=$_m;
}
return abs($_n);
}以下函数更准确
function GCD($num1, $num2) {
/* 找到两个数字的最大公约数 */
while ($num2 != 0){
$t = $num1 % $num2;
$num1 = $num2;
$num2 = $t;
}
return $num1;
}这是我用于获取多个数字的 GCD 的解决方案。
<?php
/*
* function gcd()
*
* 返回两个数字的最大公约数
* 对 gmp_gcd() 进行了测试
*/
function gcd($a, $b)
{
if ($a == 0 || $b == 0)
return abs( max(abs($a), abs($b)) );
$r = $a % $b;
return ($r != 0) ?
gcd($b, $r) :
abs($b);
}
/*
* function gcd_array()
*
* 获取数组中数字的最大公约数
*/
function gcd_array($array, $a = 0)
{
$b = array_pop($array);
return ($b === null) ?
(int)$a :
gcd_array($array, gcd($a, $b));
}
?>我想要这个功能，而无需安装扩展。
所以，我编写了一个脚本来找出最大公约数
<?php
// 我们的分数 3/12 可以写得更好
$numerator = 3;
$denominator = 12;
/**
* @param int $num
* @return array $num 的公因数
*/
function getFactors($num)
{
$factors = [];
// 获取分子的因数
for ($x = 1; $x <= $num; $x ++) {
if ($num % $x == 0) {
$factors[] = $x;
}
}
return $factors;
}
/**
* @param int $x
* @param int $y
*/
function getGreatestCommonDenominator($x, $y)
{
// 首先获取分子和分母的公因数
$factorsX = getFactors($x);
$factorsY = getFactors($y);
// 公因数将出现在两个数组中，所以获取交集
$commonDenominators = array_intersect($factorsX, $factorsY);
// 最大公因数是最大的数字（数组中的最后一个）
$gcd = array_pop($commonDenominators);
return $gcd;
}
// 用 gcd 除分子和分母以获得简化的分数
$gcd = getGreatestCommonDenominator($numerator, $denominator);
echo ($numerator / $gcd) .'/'. ($denominator / $gcd); // 我们可以使用除法（/），因为我们知道结果是整数 :-)
您可以在此处查看运行情况：://3v4l.org/uTucY如果您不将 a 或 b 视为可能的负数，GCD 函数可能会返回一个负的 GCD，这不是最大公约数，因此像这样的函数可能更好。这考虑了 (-3)-(-6) 的简化，其中 -3 和 -6 的 gcd 将导致 3，而不是其他函数中的 -3。(-3)-(-6) 是 (-1)-(-2) 而不是 (1)-(2)
function eGCD($a,$b){
if($a < 0) $a=0-$a;
if($b < 0 ) $b=0-$b;
if($a == 0 || $b == 0) return 1;
if($a == $b) return a;
do{
$rest=(int) $a % $b; $a=$b; $b=$rest;
}while($rest >0);
return $a;
}无需仅仅为了 GCD 函数而编译 gmp 函数... 使用这个代替
function GCD($num1, $num2) {
/* 找到两个数字的最大公约数 */
if ($num1 < $num2) {
$t = $num1;
$num1 = $num2;
$num2 = $t;
}
while ($t = ($num1 % $num2) != 0) {
$num1 = $num2;
$num2 = $t;
}
return $num2;
}function gcd($a,$b)
{
return $b ? gcd($b, $a%$b) : $a;
}
这个速度很快，代码很短，也很容易记住。如果 $b 为零，返回 a，否则交换并取模。