Euclid's Algorithm
Euclid's Algorithm is one of the oldest algorithms known to
mankind. It was found in Euclid's Elements, something dates back to 300 B.C.
When Euclid came up with the algorithm, mathematics was not
known as it is today; in fact, he used geometrical methods in his discovery, as
algebra was not known at that time, as a branch of mathematics.
Euclid's algorithm is used to find the HCF - Highest Common
Factor - or GCD - Greatest Common Divider - of two numbers.
The following animation shows how it determines the HCF of two
numbers:
The corresponding flow chart for the Euclid algorithm is as follows:
Please work out the following questions to complement what you have just learnt.