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 16 and 36 is 4