Skip to content

Instantly share code, notes, and snippets.

@GaryJones
Last active September 15, 2022 14:46
Show Gist options
  • Save GaryJones/4498654 to your computer and use it in GitHub Desktop.
Save GaryJones/4498654 to your computer and use it in GitHub Desktop.
Class for calculating the greatest common factor of two or more numbers.
<?php
/**
* Greatest Common Factor.
*
* @package GreatestCommonFactor
* @author Gary Jones
* @link http://code.garyjones.co.uk/greatest-common-factor-class/
* @license http://gamajo.mit-license.org/2011
*/
/**
* GreatestCommonFactor is a class for finding the greatest common factor of two
* or more numbers.
*
* Bit hat tip to http://www.calculatorsoup.com/calculators/math/gcf.php for the
* initial logic.
*
* @package GreatestCommonFactor
* @author Gary Jones
* @license http://gamajo.mit-license.org/2011
*/
class GreatestCommonFactor
{
/**
* Holds all values.
*
* @var array
*/
protected $values = array();
/**
* Grab values into array.
*
* @param int|array $arg Accepts either an array of integers, or
* multiple integer arguments
*/
public function __construct($arg)
{
if (func_num_args() > 1) {
$this->values = func_get_args();
} else {
$this->values = (array) $arg;
}
}
/**
* Add an extra value to the collection.
*
* @param int $value
*/
public function add($value) {
array_push($this->values, $value);
}
/**
* Do the calculation of the GCF.
*
* @return int
*/
public function calculate()
{
$this->validate();
// Count the number of values in the array
$num_values = count($this->values);
// Get the first 2 values in the array
$x = current($this->values);
$y = next($this->values);
// set up a for-loop to check through all of the values in the array
// the first pass will check two numbers then each additional pass will
// check one more, giving ($num_values - 1) passes
for ($i = 1; $i < $num_values; $i++) {
// Set up the larger and smaller of the values
$a = max($x, $y);
$b = min($x, $y);
$c = 1;
// Find the greatest common factor of $a and $b
// It will be found when $c == 0
do {
$c = $a % $b;
// Capture last value of $b as the potential last GCF result
$gcf = $b;
// If $c did not equal 0 we need to repeat with the values held
// in $b and $c. At this point $b is higher than $c so we set up
// for the next iteration, setting $a to the higher number and
// $b to the lower number
$a = $b;
$b = $c;
} while ($c != 0);
// If $c == 0 then we have found the GCF of 2 numbers
// now set up to find the GCF of the last GCF we found and the next value in the array()
$x = $gcf;
$y = next($this->values);
}
return $gcf;
}
/**
* Check that the values to calculate the result from are all valid.
*
* @throws BadMethodCallException
* @throws InvalidArgumentException
*/
protected function validate() {
// Check we have at least two values
if (count($this->values) < 2) {
throw new BadMethodCallException('Not enough values submitted to find the greatest common factor.');
}
// Loop through each value to check it is valid
foreach ($this->values as $value) {
if (is_int($value) && $value > 0) {
throw new InvalidArgumentException('The value of ' . $value . ' is invalid for finding the greatest common factor.');
}
}
}
}
<?php
// Use an array
$values = array(225, 45, 15, 540); // Maybe pulled from external source
$gcf = new GreatestCommonFactor($values);
echo 'GCF = ' . $gcf->calculate();
// Outputs: GCF = 15
// Use a comma-separated list of numbers
$gcf = new GreatestCommonFactor(225, 45, 15, 540);
echo 'GCF = ' . $gcf->calculate();
// Outputs: GCF = 15
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment