What is HCF and GCD? | Maths Explanation for Python Kids
Highest Common Factor or Greatest Common Divisor is the highest-valued-factor
or greatest-valued-divisor common to a set of numbers.
In this Python math project, we'll explore how to find the Highest Common Factor (HCF) and Greatest Common Divisor (GCD) of numbers.
This tutorial is perfect for primary school students learning to code with 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
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; File, New File.
Call it FindHCF.py
Type out the adjoining Python code for finding Highest Common Factor (H.C.F.) or Greatest Common Divisor.
Note: You can comment out the Python code for the main class from the previous lesson if you have been following.
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")