The greatest common divisor of two positive non-zero integers is the highest number which divides both numbers exactly. The Greek mathematician, Euclid, devised an algorithm to find the GCD. He said:
Compare the two numbers - if they are equal then this is the GCD so stop. Otherwise subtract the smaller from the greater and keep repeating this process until they become equal - you then have the GCD so stop.
Use Euclid's algorithm as the basis for a program design to find the GCD of two input integers.
<?
// generate two positive even numbers
$num1 = rand(1, 50) * 2;
$num2 = rand(1, 50) * 2;
// save these for later use
$num1_orig = $num1;
$num2_orig = $num2;
// if the numbers aren't the same
while ($num1 <> $num2)
{
// check which number is highest
if ($num1 > $num2)
// the first is larger
$num1 -= $num2;
else
// the second is larger
$num2 -= $num1;
}
// show the original numbers and the GCD
echo 'The greatest common divisor of ' . $num1_orig . ' and ' . $num2_orig . ' is ' . $num1;
?>Which produces:
The greatest common divisor of 42 and 34 is 2