这是一个优雅的递归解决方案
<?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 — 计算最大公约数
计算num1和num2的最大公约数。即使其中一个或两个输入操作数为负数，结果也始终为正数。
num1一个GMP对象，一个int，或一个string，可以解释为数字，其逻辑与在gmp_init()中使用字符串并自动检测基数（即base等于0时）相同。
num2一个GMP对象，一个int，或一个string，可以解释为数字，其逻辑与在gmp_init()中使用字符串并自动检测基数（即base等于0时）相同。
一个正的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;
}这是我获取多个数字的最大公约数的解决方案。
<?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 = getGreatestCommonDenominator($numerator, $denominator);
echo ($numerator / $gcd) .'/'. ($denominator / $gcd); // 我们可以使用除法 (/)，因为我们知道结果是整数 :-)
你可以在此处看到运行结果 https://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，否则交换并取模。