Geek Answers Handbook

Looking for a GCD (largest common factor) of more than two integers?

I already have a function that finds a GCD of 2 numbers.

function getGCDBetween($a, $b) { while ($b != 0) { $m = $a % $b; $a = $b; $b = $m; } return $a; }

But now I would like to expand this function to find GCD from N points. Any suggestion?

+6
source share
7 answers

There is a more elegant way to do this:

 // Recursive function to compute gcd (euclidian method) function gcd ($a, $b) { return $b ? gcd($b, $a % $b) : $a; } // Then reduce any list of integer echo array_reduce(array(42, 56, 28), 'gcd'); // === 14

If you want to work with floating points, use the approximation:

 function fgcd ($a, $b) { return $b > .01 ? fgcd($b, fmod($a, $b)) : $a; // using fmod } echo array_reduce(array(2.468, 3.7, 6.1699), 'fgcd'); // ~= 1.232

You can use closure in PHP 5.3:

 $gcd = function ($a, $b) use (&$gcd) { return $b ? $gcd($b, $a % $b) : $a; };
+13
source

I have to work a little, but this is what I found .

gcd of three numbers can be calculated as gcd (a, b, c) = gcd (gcd (a, b), c) or in some other way, using commutativity and associativity. This can be expanded to any number of numbers.

You can use something like the following:

 function multiGCD($nums) { $gcd = getGCDBetween($nums[0], $nums[1]); for ($i = 2; $i < count($nums); $i++) { $gcd = getGCDBetween($gcd, $nums[$i]); } return $gcd; }
+7
source

You can try

 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($array, $a = 0) { $b = array_pop($array); return ($b === null) ? (int) $a : gcd_array($array, gcd($a, $b)); } echo gcd_array(array(50, 100, 150, 200, 400, 800, 1000)); // output 50
+2
source

Take the GCD of numbers 1 and 2, and then the GCD of this and the number 3, etc.

+2
source

I found a solution, but it looks a little ugly:

1) by checking each divisor of each integer

2) find a larger integer in each array

 function getAllDivisorsOf($n) { $sqrt = sqrt($n); $divisors = array (1, $n); for ($i = 2; ($i < $sqrt); $i++) { if (($n % $i) == 0) { $divisors[] = $i; $divisors[] = ($n / $i); } } if (($i * $i) == $n) { $divisors[] = $i; } sort($divisors); return $divisors; } function getGCDFromNumberSet(array $nArray) { $allDivisors = array (); foreach ($nArray as $n) { $allDivisors[] = getAllDivisorsOf($n); } $allValues = array_unique(call_user_func_array('array_merge', $allDivisors)); array_unshift($allDivisors, $allValues); $commons = call_user_func_array('array_intersect', $allDivisors); sort($commons); return end($commons); } echo getGCDFromNumberSet(array(50, 100, 150, 200, 400, 800, 1000)); // 50

Any better idea?

+1
source

You can store numbers in an array and / or database and read from there. And then in a loop you can modularly split the elements of an array.

0
source

You can also use the gmp library:

 <?php $gcd = gmp_gcd( '12', '21' ); echo gmp_strval( $gcd ); ?>
0
source

More articles:


All Articles