Robson » Little Red Book » Greatest common divisor

Chapter 5 - Question 3

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.

Solution 1

<?
   // 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 18 and 74 is 2

Log

© 2004-17 robson | cc unless stated