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
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|
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 your function using the following test plan:
|Test #||Input Values||Expected Output||Actual Output|