# 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 18 is 6

## Log

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