here is an elegant recursive solution
<?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.
Положительный НОД чисел
num1 и num2.
Пример #1 Пример использования gmp_gcd()
<?php
$gcd = gmp_gcd("12", "21");
echo gmp_strval($gcd) . "\n";
?>Результат выполнения приведённого примера:
3
here is an elegant recursive solution
<?php
function gcd($a,$b) {
return ($a % $b) ? gcd($b,$a % $b) : $b;
}
?>The previous function returns just 1 under php 5.2.4 but the following seems to work (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);
}The following function is more accurate:
function GCD($num1, $num2) {
/* finds the greatest common factor between two numbers */
while ($num2 != 0){
$t = $num1 % $num2;
$num1 = $num2;
$num2 = $t;
}
return $num1;
}Here's my solution for getting the GCD of several numbers.
<?php
/*
* function gcd()
*
* returns greatest common divisor
* between two numbers
* tested against 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()
*
* gets greatest common divisor among
* an array of numbers
*/
function gcd_array($array, $a = 0)
{
$b = array_pop($array);
return ($b === null) ?
(int)$a :
gcd_array($array, gcd($a, $b));
}
?>I wanted this functionality without having to install the extension.
So here's a script I wrote to find out the greatest common denominator:
<?php
// Our fraction, 3/12, could be written better
$numerator = 3;
$denominator = 12;
/**
* @param int $num
* @return array The common factors of $num
*/
function getFactors($num)
{
$factors = [];
// get factors of the numerator
for ($x = 1; $x <= $num; $x ++) {
if ($num % $x == 0) {
$factors[] = $x;
}
}
return $factors;
}
/**
* @param int $x
* @param int $y
*/
function getGreatestCommonDenominator($x, $y)
{
// first get the common denominators of both numerator and denominator
$factorsX = getFactors($x);
$factorsY = getFactors($y);
// common denominators will be in both arrays, so get the intersect
$commonDenominators = array_intersect($factorsX, $factorsY);
// greatest common denominator is the highest number (last in the array)
$gcd = array_pop($commonDenominators);
return $gcd;
}
// divide the numerator and denomiator by the gcd to get our refactored fraction
$gcd = getGreatestCommonDenominator($numerator, $denominator);
echo ($numerator / $gcd) .'/'. ($denominator / $gcd); // we can use divide (/) because we know result is an int :-)
Which you can see running here https://3v4l.org/uTucYIf you do not consier a or b as possible negative numbers, a GCD funktion may return a negative GCD, wich is NOT a greatest common divisor, therefore a funktion like this may be better. This considers the simplyfying of (-3)-(-6) where gcd on -3 and -6 would result in 3, not -3 as with the other function. (-3)-(-6) is (-1)-(-2) NOT (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;
}No need to compile gmp functions in just for the GCD function... use this one instead:
function GCD($num1, $num2) {
/* finds the greatest common factor between two numbers */
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;
}
This is pretty fast and short, also easy to remember. If $b is zero, return a, otherwise swap and mod.