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

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

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
#2 a: 45
b: 30
#3 a: 78
b: 24
#4 a: 60
b: 20
#5 a: 100
b: 21
#6 a: 96
b: 72
#7 a: 72
b: 96

Did you like this challenge?

Click on a star to rate it!

Average rating 4.2 / 5. Vote count: 6

No votes so far! Be the first to rate this post.

As you found this challenge interesting...

Follow us on social media!

Tagged with: