Python Highest Common Factor (HCF / GCD)

Calculate the Highest Common Factor (HCF) or Greatest Common Divisor (GCD) of two numbers using the Euclidean algorithm.

Try Python Highest Common Factor (HCF / GCD) Code

How it Works

The Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD), is the largest positive integer that divides two or more integers without leaving a remainder.

The Euclidean algorithm is an extremely efficient method for computing HCF. It states that the GCD of two numbers also divides their difference.

In Python, we implement this iteratively using a while loop where we continuously replace the larger number with the remainder of their division.

Source Code

Euclidean loop implementation to find HCF/GCD of two numbers.

hcf_gcd.py

Try in Editor

def find_gcd(a, b):
    # Euclidean Algorithm
    while b != 0:
        a, b = b, a % b
    return a

print("GCD of 36 and 60 is:", find_gcd(36, 60))
print("GCD of 17 and 5 is: ", find_gcd(17, 5))

Terminal Output

GCD of 36 and 60 is: 12
GCD of 17 and 5 is:  1

Real-world Applications

Fraction simplification and math engines
Cryptography algorithms (like RSA private keys generation)
Designing periodic event schedules

Frequently Asked Questions

Does Python have a built-in GCD function?

Yes! Python's standard library contains `math.gcd(a, b)` which uses a compiled C implementation under the hood.

More Examples

Python Lowest Common Multiple (LCM)

Find the Lowest Common Multiple (LCM) of two numbers using their HCF relation in Python.

Python Simple Calculator Script

Build a basic calculator in Python. Learn how to map mathematical operators, take user execution flows, and handle logic natively.

Recommended Python Resources

Expand your knowledge with related interactive tutorials, cheat sheets, and code comparisons.

Python Tutorial

Python Loops

Learn how to use Python loops to iterate over data. Master for loops, while loops, break, continue, and loop best practices with interactive examples.

View Resource

How-To Guide

How to Sort a List in Python

Learn how to sort a list in Python using the sort() method and the sorted() function. Discover custom key sorting and reverse order examples.

View Resource

Cheat Sheet

Python String Methods

A complete reference guide for Python string manipulation. Master formatting, searching, splitting, replacing, and checking string properties.

View Resource

Language Compare

Python vs JavaScript: Which Programming Language is Best?

A comprehensive comparison between Python and JavaScript. Explore syntax differences, performance, use cases (backend vs frontend), and coding examples.

View Resource