gmp_gcd

(PHP 4 >= 4.0.4, PHP 5)

gmp_gcd -- Calculate GCD

Description

resource gmp_gcd ( resource a, resource b )

Calculate greatest common divisor of a and b. The result is always positive even if either of, or both, input operands are negative.

例子 1. gmp_gcd() example

<?php
$gcd
= gmp_gcd("12", "21");
echo
gmp_strval($gcd) . "\n";
?>

The printout of the above program will be:

3

add a note add a note User Contributed Notes
bigkm1 at gmail dot com
26-Aug-2006 12:33
here is an elegant recursive solution
<?php   

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

?>
scr02001 at student dot mdh dot se
16-Aug-2003 09:58
If 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;
}
Ludwig Heymbeeck
13-Jan-2003 02:33
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;
}
x-empt-php dot net at ispep dot cx
07-Jul-2002 02:16
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;
}