*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 82 and 76 is 2

- Mar 31, 2005 - Added solution 1.

© 2004-19 robson | cc unless stated