Fast HCF Python Code | Efficient GCD Algorithm Tutorial

Fast Python Code to Find HCF (GCD)

This tutorial demonstrates an efficient Python method to calculate the Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD). Using prime factorization and loop optimization, students can learn how Python handles numerical sorting and divisor checks.
The H.C.F. code in Python from the previous Finding HCF and GCD in Python lesson could get a bit slow if we run into a prime number and this prime number becomes the loop range.

Let's see how we can fix this and make a fast Python algorithm to find HCF:

Step 1:

Do a numerical sort on the resulting set so its first member is the smallest in the set.

Step 2:

Find the factors of the first number in the set.

Step 3:

Iteratively check through the set of numbers with the factors from Step 2 to make sure it is common to all.

Step 4:

For each common factor, divide every member of the number set by the common factor.

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 - Fast Find HCF

As a fun practice exercise, feel free to try out your own numbers, and see how the fast Python code finds the HCF of those numbers.

Python Code for Fast HCF - Module File.

# A class
class quickHCF:

    # A constructor
    def __init__(self, group):
        self.set_of_numbers = []
        self.arg_copy = []
        for val in group:
            self.set_of_numbers.append(val)
            self.arg_copy.append(val)
        # STEP 1:
        self.set_of_numbers.sort()
        self.arg_copy.sort()

        self.common_factors = []

        self.index = 2
        self.all_round_factor = False # state flag
        self.calc_result = 1

    # STEP 2:
    # does the grunt work
    # takes no arguments but requires 'set_of_numbers' to be set
    def findHCFFactors(self):
        while self.index < len(self.minimal_prime_factors):
            self.all_round_factor = True
            # STEP 3:
            for count in range(len(self.set_of_numbers)):
                if self.all_round_factor and self.arg_copy[count] % self.minimal_prime_factors[self.index] != 0:
                    self.all_round_factor = False

            # STEP 4:
            if self.all_round_factor:
                for count_off in range(len(self.set_of_numbers)):
                    self.arg_copy[count_off] /= self.minimal_prime_factors[self.index]

                self.common_factors.append(self.minimal_prime_factors[self.index])

            self.index += 1
        return None

    # Returns a scalar value of the HCF
    def getHCF(self):
        # use only direct factors of the smallest member
        from ListPrimeFactors import PrimeFactors
        self.aux = PrimeFactors(self.set_of_numbers[0])
        self.minimal_prime_factors = self.aux.onlyPrimeFactors()

        # go ahead and see which of the above factors are mutual
        self.index = 0
        self.findHCFFactors()

        #iterate through and retrieve members
        for factor in self.common_factors:
            self.calc_result *= factor

        return self.calc_result

Python Code for Fast HCF - Main Class.

#!/usr/bin/python
from FastHCF import quickHCF

# Use the fast HCF module/class
group = [20, 30, 40]
h_c_f = quickHCF(group)
answer = h_c_f.getHCF()
print("The H.C.F. of ", group, " is", answer)

print("\n\n")

I have a better version / See other versions.