Euclid’s Division Algorithm

Euclid’s division algorithm is used to calculate the Highest Common Factor (HCF) of two positive numbers. It is based on Euclid’s division lemma and can be implemented in just a few lines of high level code. You can read more about this algorithm on this page.

Euclid’s Division Algorithm: Pseudocode

INPUT a #The largest of two numbers
INPUT b #The smallest of two numbers
WHILE b > 0
   temp = b
   b = a MOD b
   a = temp
END WHILE
OUTPUT a

Trace Table

Do get a better understanding of how this algorithm works we will complete the following trace tables assuming that the two input values a and b will be a = 32 and b = 24. The output (Highest Common Factor) of this program should be 8.

Complete the trace table below to find out if this algorithm will produce the required output.

	Line Number	a	b	temp	b > 0?	OUTPUT
+–	1	32
+–	2		24
+–	3				True
+–	…

Python Code

You can now create a function called calculateHCF() that takes two parameters, a and b and returns the HCF of these two numbers using Euclid’s division algorithm.

To improve your code, you should make it work even when number b is greater than number a.

Test Plan

Test your function using the following test plan:

Test #	Input Values	Expected Output	Actual Output
#1	a: 32 b: 24	8
#2	a: 45 b: 30	15
#3	a: 78 b: 24	6
#4	a: 60 b: 20	20
#5	a: 100 b: 21	1
#6	a: 96 b: 72	24
#7	a: 72 b: 96	24