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

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 Numberabtempb > 0?OUTPUT
132
224
3True

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

Share Button
Tagged with: