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

## Log

• Mar 31, 2005 - Added solution 1.
© 2004-20 robson | cc unless stated