I saw two programs today which attempted to do this calculation by looping from 1 to the lower number, and testing if division of both numbers by that factor left a remainder. This is extremely slow when both numbers are very large, so to give an example of why it's important to find efficient algorithms, I've created a fraction simplifier by remixing my "highest common factor" program which used Euclid's algorithm. Doing a loop & divide test in Euclid's era would have taken years to compute by hand!
Algorithm courtesy of Euclid. Inspired by http://scratch.mit.edu/projects/10938828/ and http://scratch.mit.edu/projects/26377806/
