Understanding HCF and GCD in Python
The Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD), is an important concept in primary school mathematics and number theory. In this lesson, learners will explore what HCF means and how it can be calculated using a simple and interactive Python program.
This activity combines mathematics and coding, helping students understand factors while developing basic programming skills.
What Is the Highest Common Factor (HCF)? | Maths Explanation for Python Kids
The highest common factor (HCF) of two or more numbers is the largest number that divides each of them exactly, without leaving a remainder.
For example:
- The factors of 12 are: 1, 2, 3, 4, 6, 12
- The factors of 18 are: 1, 2, 3, 6, 9, 18
- The HCF of 12 and 18 is 6
In programming and computer science, HCF is often called the greatest common divisor (GCD). Both terms mean the same thing.
How to Find the Highest Common Factor (HCF) in Python
A common method for finding H.C.F. - G.C.D. is repeated factorization using only common factors.
If we have the set of numbers 30, 48 and 54 for example, their H.C.F. or G.C.D. is found thus:
Hence, H.C.F. of 30, 48 and 54 = 2 X 3 = 6
Python Code to Calculate HCF (GCD)
The Python program below calculates the HCF of two numbers by checking their common factors and identifying the highest one.
This approach is easy to understand and ideal for learning purposes.
How to Find HCF of Multiple Numbers in Python | Step-by-step Guide.
We shall follow the steps below in our Python algorithm for finding HCF.
Step 1:
Do a numerical sort on the set so its first member is the smallest in the set.
Step 2:
Starting with 2, iteratively check through the set of numbers for a common factor.
Step 3:
For each common factor, divide every member of the number set by the common factor.
Step 4:
Repeat from step 2 recursively until there are no more common factors.
Create a new Python Module File;
Call it FindHCF.py
Type out the adjoining Python code for finding Highest Common Factor (H.C.F.) or Greatest Common Divisor.
Step-by-Step Explanation of the HCF Algorithm
- The program accepts several numbers as input.
- It checks each number from 1 up to the smaller of the two values.
- For each number, it tests whether it divides both inputs exactly.
- If it does, it is a common factor.
- The largest common factor found is stored as the highest common factor (HCF).
- The final result is displayed to the user.
This step-by-step Python algorithm helps learners clearly see how common factors are identified and compared.
HCF vs GCD: What Is the Difference?
There is no difference between HCF and GCD in meaning.
- HCF (Highest Common Factor) is commonly used in school mathematics.
- GCD (Greatest Common Divisor) is more commonly used in programming and computer science.
When working with Python or other programming languages, you may see either term used.
Why Learn HCF Using Python?
Learning how to calculate HCF using Python helps students:
- Strengthen their understanding of factors and divisibility
- Apply logical thinking to solve math problems
- See how mathematical ideas are translated into computer algorithms
- Build confidence with basic Python coding
This makes the activity suitable for primary school learners, beginners, and anyone new to coding math concepts.
Who Is This Python HCF Activity For?
This interactive Python HCF calculator is suitable for:
- Primary school students learning factors
- Teachers introducing coding into math lessons
- Beginners learning Python through math projects
- Anyone wanting a simple explanation of HCF and GCD
Summary: Python Algorithm to Calculate HCF (GCD)
In this lesson, you learned:
- The meaning of highest common factor (HCF)
- How HCF relates to greatest common divisor (GCD)
- How to calculate HCF using a simple Python program
- How math concepts can be implemented through coding
By combining number theory with Python, learners gain a deeper understanding of both subjects in a practical and engaging way.
So! Python Fun Practice Exercise - Find HCF
As a fun practice exercise, feel free to try out your own numbers, and see how the Python code finds the HCF of those numbers.
Python Code for Find HCF - Module File.
class findHCF:
# A constructor
def __init__(self, group):
self.set_of_numbers = [] # will hold the the values to be sent in
# make copy of argument
for value in group:
self.set_of_numbers.append(value)
# STEP 1:
self.set_of_numbers.sort() # sort ascending
self.common_factors = [] # for housing all common factors
self.all_round_factor = False # boolean state flag
self.calc_result = 1
# does the grunt work
# takes no arguments but requires '@set_of_numbers' to be set
def findHCFFactors(self):
# use the smallest in the set for the range
while self.index < self.set_of_numbers[0]:
self.index += 1
# Check for factors common to every member of 'set_of_numbers'
self.all_round_factor = True
# STEP 2:
for count in range(len(self.set_of_numbers)):
if self.all_round_factor and self.set_of_numbers[count] % self.index != 0:
self.all_round_factor = False
# STEP 3:
# Divide every member of 'set_of_numbers by each common factor
if self.all_round_factor:
for count_off in range(len(self.set_of_numbers)):
self.set_of_numbers[count_off] /= self.index
self.common_factors.append(self.index)
# STEP 4:
return self.findHCFFactors()
return None
# Returns a scalar value of the HCF
def getHCF(self):
self.index = 1
self.findHCFFactors()
#iterate through and retrieve members
for factor in self.common_factors:
self.calc_result *= factor
return self.calc_result
Python Code for Find HCF - Main Class.
from HCF import findHCF
# Use the HCF module/class
group = [20, 30, 40]
hcf = findHCF(group)
answer = hcf.getHCF()
print ("The H.C.F. of ", group, " is", answer)
print("\n\n")