RobsonLittle 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 42 and 34 is 2

Log

© 2004-20 robson | cc unless stated