gmp_gcd

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

gmp_gcd最大公約数を計算する

説明

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

num1num2 の最大公約数を計算します。 引数のどちらかまたは両方が負の場合でも結果は常に正となります。

パラメータ

num1

GMP オブジェクト、整数、あるいは数値に変換可能な数値形式の文字列。

num2

GMP オブジェクト、整数、あるいは数値に変換可能な数値形式の文字列。

戻り値

num1num2 の両方を割り切ることができる正の数を GMP 数で返します。

例

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

3

参考

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;
}

?>
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));
}

?>
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
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);
}
-1
me at abiusx dot com
1 year 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.
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;
}
-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;
}
-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;
} 