Wednesday, March 21, 2012

Jessica's solution to a loopy problem

A well known algorithm, taught in Number Theory classes at tertiary level, is Euclid’s algorithm for finding the Greatest Common Divisor (GCD) of two numbers. In Australia, we tend to refer to the GCD as the Highest Common Factor. In this post, I describe the algorithm and present a year 8 student’s program that implements it.

The Algorithm
To illustrate what the GCD of two numbers is, let’s consider a 21 x 15 rectangle.