Find HCF and GCD in Python | Primary School Math Projects

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:

Steps for calculating HCF using factorization method

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 (Greatest Common Divisor).(H.C.F.)

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.

# A class
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.

#!/usr/bin/python
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")

I have a better version / See other versions.