How to Find HCF and LCM in Python (5 Easy Methods)

Finding the HCF and LCM of two numbers is one of the first real programs most students write once they move past printing text. It shows up in school assignments, in first-year college labs, and in coding interviews, because it quietly tests loops, conditions, and a little number sense all at once.

The good news is that Python gives you more than one path to the answer. You can let a built-in function do the whole job in a single line, or you can write the logic yourself and understand exactly what is happening under the hood. Both are worth knowing: one for real work, one for learning.

In this guide we will cover five methods to find the HCF and LCM in Python: the built-in math.gcd and math.lcm functions, the Euclidean algorithm with a while loop, a recursive version, a plain brute-force loop, and the neat formula that turns any HCF into an LCM. Every example uses the same two numbers, 48 and 18, so you can follow the answer all the way through.

What Are HCF and LCM? A Quick Refresher

Before we write any code, let us be sure the two ideas are clear, because the code only makes sense once the maths does.

• HCF (Highest Common Factor): the largest number that divides both numbers exactly. It is also called the GCD, or Greatest Common Divisor. Python uses the name gcd.
• LCM (Lowest Common Multiple): the smallest number that both numbers divide into exactly.

Take 48 and 18. The factors of 48 are 1, 2, 3, 4, 6, 8, 12, 16, 24, 48. The factors of 18 are 1, 2, 3, 6, 9, 18. The common factors are 1, 2, 3, and 6, so the highest of them, the HCF, is 6. The smallest number that both 48 and 18 divide into is 144, so the LCM is 144.

The One Formula That Ties Them Together

Here is the single most useful fact in this whole topic. For any two positive numbers, the HCF multiplied by the LCM always equals the two numbers multiplied together.

Method 1: The Easy Way With math.gcd and math.lcm

Python ships with a math module that already knows how to do this. The math.gcd function gives you the HCF, and math.lcm gives you the LCM. This is the version you should use in real projects.

import math

a = 48
b = 18

hcf = math.gcd(a, b)   # Highest Common Factor
lcm = math.lcm(a, b)   # Lowest Common Multiple

print("HCF:", hcf)     # HCF: 6
print("LCM:", lcm)     # LCM: 144

Method 2: HCF With the Euclidean Algorithm (While Loop)

If you want to understand how the HCF is actually found, the Euclidean algorithm is the classic approach and it is beautifully short. The idea is simple: keep replacing the larger number with the remainder of dividing the two, until the remainder is zero. Whatever is left is the HCF. This kind of clever, efficient trick is the heart of algorithmic thinking, which we build up step by step in our data structures and algorithms course.

def find_hcf(a, b):
    while b:
        a, b = b, a % b
    return a

print(find_hcf(48, 18))   # 6

How it works, step by step

1. Start with a = 48 and b = 18.
2. 48 mod 18 is 12, so a becomes 18 and b becomes 12.
3. 18 mod 12 is 6, so a becomes 12 and b becomes 6.
4. 12 mod 6 is 0, so a becomes 6 and b becomes 0.
5. b is now 0, the loop stops, and a, which is 6, is the HCF.

The line a, b = b, a % b swaps and updates both values in one go. This is why the algorithm handles cases where a is smaller than b without any extra checks.

Method 3: HCF With Recursion

The same Euclidean idea can be written with recursion, where the function calls itself instead of using a loop. Some people find this version reads more like the definition of the problem.

def find_hcf(a, b):
    if b == 0:
        return a
    return find_hcf(b, a % b)

print(find_hcf(48, 18))   # 6

The base case is when b reaches 0, and at that point a holds the answer. Until then, the function keeps calling itself with the smaller pair, exactly like the loop did.

Method 4: HCF and LCM With a Simple Loop

This is the most beginner-friendly method because it copies how you would do it by hand. To find the HCF, check every number from 1 up to the smaller of the two, and remember the largest one that divides both.

def find_hcf(a, b):
    hcf = 1
    for i in range(1, min(a, b) + 1):
        if a % i == 0 and b % i == 0:
            hcf = i
    return hcf

print(find_hcf(48, 18))   # 6

You can find the LCM with a loop too. Start at the larger number and keep going up until you hit a value that both numbers divide into exactly.

def find_lcm(a, b):
    greater = max(a, b)
    while True:
        if greater % a == 0 and greater % b == 0:
            return greater
        greater += 1

print(find_lcm(48, 18))   # 144

These loops are easy to read, but they get slow for very large numbers because they test one value at a time. For anything beyond practice, prefer the built-in or the formula method.

Method 5: Finding LCM From the HCF

Remember the golden rule. Since HCF times LCM equals a times b, you can rearrange it to get the LCM directly: LCM equals a times b, divided by the HCF. This is fast and works on any Python version, since it only needs an HCF function.

def find_hcf(a, b):
    while b:
        a, b = b, a % b
    return a

def find_lcm(a, b):
    return a * b // find_hcf(a, b)

print(find_lcm(48, 18))   # 144

Notice the double slash. That is integer division, which keeps the result a whole number instead of a decimal. Since the HCF always divides a times b exactly, the answer is always clean.

Bonus: HCF and LCM of a List of Numbers

What if you have more than two numbers? You can apply the two-number logic across the whole list using reduce, which carries the running answer from one pair to the next.

import math
from functools import reduce

numbers = [12, 18, 24]

hcf_all = reduce(math.gcd, numbers)
lcm_all = reduce(math.lcm, numbers)

print("HCF of list:", hcf_all)   # 6
print("LCM of list:", lcm_all)   # 72

reduce takes the first two numbers, finds their answer, then combines that answer with the next number, and so on. It is the cleanest way to handle a whole list at once.

Which Method Should You Use?

All five methods give the same answer for 48 and 18. The one you pick depends on whether you are shipping real code or learning the logic for an exam.

• Real projects: use math.gcd and math.lcm. They are fast, tested, and clear.
• Learning or interviews: write the Euclidean while loop, since it shows you understand the algorithm.
• Old Python versions: use the formula method to build the LCM from your own HCF.
• First time seeing this: start with the simple loop, then upgrade once the idea clicks.

A Complete Program (Copy-Paste Ready)

Here is a small program that asks the user for two numbers and prints both results using the built-in functions.

import math

a = int(input("Enter the first number: "))
b = int(input("Enter the second number: "))

print("HCF of", a, "and", b, "is", math.gcd(a, b))
print("LCM of", a, "and", b, "is", math.lcm(a, b))

Common Mistakes to Avoid

• Using a single slash for the LCM: a * b / find_hcf(a, b) returns a decimal like 144.0. Use double slash for a clean whole number.
• Forgetting to update b in the while loop: if you leave out a, b = b, a % b, the loop never ends.
• Assuming math.lcm exists everywhere: it needs Python 3.9 or newer. On older versions, build it from the HCF.
• Passing zero: the HCF of a number and 0 is the number itself, which is correct, but the brute-force LCM loop will run forever if either input is 0. Guard against it if users can type anything.

Frequently Asked Questions

Keep Building Your Python Skills

Small programs like this are how strong Python habits are built, one clear idea at a time. If you enjoyed working through the logic, try our beginner-friendly walkthrough on Python for beginners, or stretch further with the classic Armstrong number program. When you are ready for a guided path with a real teacher, our Python from the ground up course covers fundamentals exactly like these, and our live coding courses take learners aged 6 to 67 from first line of code to confident problem solver.

Related reading

• Python for Beginners
• How to Write a Leap Year Program in Python
• Armstrong Number in Python