HCF and LCM algorithms

In this Python challenge we will write two functions to calculate and return the Highest Common Factor (HCF) and the Lowest Common Multiple (LCM) of two numbers.

Highest Common Factor (HCF)


Note that the HCF is also known as the GCD (Greatest Common Divisor).

To calculate the HCF of two numbers we will write a function based on Euclid’s Division Algorithm. Your function called HCF() will take two parameters and will be based on the following flowchart:
Flowchart-HCF-Function

Python Code


Create the HCF() function on the Python trinket below:

Lowest Common Multiple


Once we have worked out the HCF of two numbers we can easily calculate their Lowest Common Multiple (LCM). The LCM of two numbers a and b is their product divided by their HCF:

LCM(a, b) = ab/HCF(a,b)

Your task is to create a new Python function called LCM() that takes two parameters a and b and returns the LCM of the two numbers using the above formula.

Test Plan


Use the following test plan to test both the HCF() and LCM() functions.

Test # Input Values Expected Output Actual Output
#1 a: 32
b: 24
HCF: 8
LCM: 96
#2 a: 45
b: 30
HCF: 15
LCM: 90
#3 a: 78
b: 24
HCF: 6
LCM: 312
#4 a: 60
b: 20
HCF: 20
LCM: 60
#5 a: 100
b: 21
HCF: 1
LCM: 2100
#6 a: 96
b: 72
HCF: 24
LCM: 288
Share Button