略微加速

PHP官方手册 - 互联网笔记

PHP - Manual: gmp_gcd

2024-12-25

gmp_gcd

(PHP 4 >= 4.0.4, PHP 5, PHP 7, PHP 8)

gmp_gcdCalculate GCD

说明

gmp_gcd(GMP|int|string $num1, GMP|int|string $num2): GMP

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

参数

num1

GMP 对象或 int ,或数字string

num2

GMP 对象或 int ,或数字string

返回值

A positive GMP number that divides into both num1 and num2.

范例

示例 #1 gmp_gcd() example

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

以上例程会输出:

3

参见

add a noteadd a note

User Contributed Notes 8 notes

up
11
bigkm1 at gmail dot com
15 years ago
here is an elegant recursive solution
<?php   

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

?>
up
2
sean__remove__ at eternalrise_r_emove__ dot com
13 years ago
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));
}

?>
up
0
delboy1978uk at gmail dot com
4 years ago
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/uTucY
up
0
limas at kultur-online dot at
14 years ago
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);
}
up
-1
me at abiusx dot com
2 years ago
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.
up
0
Ludwig Heymbeeck
19 years ago
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;
}
up
-1
scr02001 at student dot mdh dot se
18 years ago
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;
}
up
-5
x-empt-php dot net at ispep dot cx
19 years ago
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;
}

官方地址:https://www.php.net/manual/en/function.gmp-gcd.php

北京半月雨文化科技有限公司.版权所有 京ICP备12026184号-3