LCM & HCF Calculator
Enter 2 to 6 numbers — get LCM, HCF, prime factorisations and step-by-step working in 3 methods
Solution Summary
All 3 Methods — Comparison
Prime Factor Breakdown
Division Method Table
Step-by-Step Working
What Are LCM and HCF?
Definitions, relationship, key properties and why these concepts appear everywhere in maths and daily life
The Highest Common Factor (HCF) — also called Greatest Common Divisor (GCD) or Greatest Common Factor (GCF) — is the largest positive integer that divides each of the given numbers without leaving a remainder. The HCF of 12 and 18 is 6 because 6 is the largest number that divides both exactly.
The Least Common Multiple (LCM) is the smallest positive integer that is divisible by all of the given numbers. The LCM of 12 and 18 is 36 because 36 is the smallest number that both 12 and 18 divide into exactly. Every common multiple of the numbers is a multiple of the LCM.
HCF and LCM are used in simplifying fractions (HCF to reduce, LCM to add/subtract), scheduling problems (when will two periodic events align?), gear ratios, tiling problems, music rhythm theory, and computer science (hash tables, memory alignment, and cyclic redundancy checks). They are among the oldest and most practically useful ideas in mathematics.
Three Methods — When to Use Each
Prime Factorisation, Division Method and Euclidean Algorithm compared with examples and use cases
| Method | Approach | Best When | Limitation |
|---|---|---|---|
| Prime Factorisation Most educational | Express each number as product of primes; HCF = min powers, LCM = max powers | Numbers up to ~200; teaching/learning; 3+ numbers | Slow for large numbers; finding prime factors can be tedious |
| Division Method (Ladder) | Divide all numbers by common prime factors; HCF = product of divisors, LCM = product of all primes used | Finding LCM of 3+ numbers; exam problems | Slightly mechanical; easy to miss a prime factor |
| Euclidean Algorithm Fastest for 2 numbers | GCD(a,b) = GCD(b, a mod b) until remainder = 0; then LCM = a×b / HCF | Large numbers; two numbers; programming | Only directly gives HCF of two numbers at a time |
| Listing Multiples/Factors | List multiples of each number; LCM = first common multiple. List factors; HCF = largest common | Small numbers; mental maths; beginners | Impractical for large numbers |
Prime Factorisation Worked
12 = 2² × 3, 18 = 2 × 3². Common primes: 2 (min power 1) and 3 (min power 1). HCF = 2¹ × 3¹ = 6. All primes: 2 (max power 2) and 3 (max power 2). LCM = 2² × 3² = 36. Check: 6 × 36 = 216 = 12 × 18. ✓
Step by stepDivision Method Worked
Write 12 and 18 in a row. Divide by smallest prime that divides at least one: 2→6,9; 2→3,9; 3→1,3; 3→1,1. HCF = product of primes that divided ALL numbers = 2×3 = 6. LCM = product of ALL primes used = 2×2×3×3 = 36.
Ladder methodEuclidean Algorithm Worked
GCD(18,12): 18 = 1×12 + 6; GCD(12,6): 12 = 2×6 + 0; remainder = 0, so GCD = 6 = HCF. LCM = 18×12 / 6 = 216 / 6 = 36. The algorithm is guaranteed to terminate and is extremely fast even for numbers with hundreds of digits.
FastestLCM for Adding Fractions
To add 5/12 + 7/18, find LCM(12,18) = 36. Convert: 5/12 = 15/36, 7/18 = 14/36. Sum = 29/36. The LCM becomes the lowest common denominator (LCD). Without LCM, you'd use 12×18=216 as denominator and get larger numbers to simplify later.
FractionsLCM for Scheduling
Bus A comes every 12 minutes, Bus B every 18 minutes. Both just left at 9:00 AM. When do they next leave together? LCM(12,18) = 36 minutes later → 9:36 AM. Any problem of the form "after how long do two periodic events coincide?" is an LCM problem.
Real worldHCF for Tiling Problems
A room is 360 cm × 252 cm. What is the largest square tile that fits exactly? HCF(360, 252). 360 = 2³×3²×5, 252 = 2²×3²×7. HCF = 2²×3² = 36 cm. So 36×36 cm tiles work perfectly with no cutting. HCF gives the largest unit that fits both dimensions exactly.
Classic useHow This Calculator Works
Step-by-step: how inputs are processed, prime factorisations found, and all three methods applied
- 1
Enter 2 to 6 Positive Integers
Fill the input boxes with any positive integers from 1 to 999,999. Optional boxes (marked "opt") are skipped automatically. The preset buttons and quick chips instantly load common example sets so you can explore without typing.
- 2
Prime Factorisation of Each Number
The calculator trial-divides each number by 2, 3, 5, 7, 11 … up to its square root to find all prime factors and their powers. Results are displayed as colour-coded factor badges — common factors highlighted in green, unique factors in blue.
- 3
HCF = Min Powers, LCM = Max Powers
Across all prime factorisations: HCF takes each prime factor at its minimum exponent across all numbers. LCM takes each prime factor at its maximum exponent. For 3+ numbers, this is extended naturally — the logic is identical.
- 4
All 3 Methods Computed — Selected Method Shown in Full
Prime Factorisation, Division Method table, and Euclidean Algorithm steps are all computed. The selected method toggle controls which one gets the full step-by-step working in the steps list. The Method Comparison section always shows all three results side by side.
- 5
Verification — Golden Relationship Check
For two numbers, the calculator always verifies LCM × HCF = a × b and displays whether the check passes. Visual proportion bars show each number's prime factorisation as a proportion of the LCM, making it easy to see which factors each number contributes.
HCF(a,b) = product of common prime factors (min powers)
LCM(a,b) = product of all prime factors (max powers)
HCF × LCM = a × b (for two numbers only)
LCM(a,b,c) = LCM(LCM(a,b), c)
HCF(a,b,c) = HCF(HCF(a,b), c)
Euclidean : GCD(a,b) = GCD(b, a mod b) until b=0LCM & HCF Facts, Tricks & Real-World Uses
Fascinating properties, shortcuts, history and applications you were never taught in school
Euclid's Algorithm Is 2,300 Years Old
The Euclidean Algorithm for finding GCD appears in Euclid's Elements (c. 300 BC), making it one of the oldest algorithms still in common use. It is more efficient than prime factorisation for large numbers — finding GCD(1,000,000,007 and 998,244,353) takes only a few steps by repeated division, while factorising those numbers would take far longer.
LCM Powers All Fraction Arithmetic
Whenever you add or subtract fractions with different denominators in school, you are finding an LCM — specifically the Lowest Common Denominator (LCD), which is exactly LCM(denominators). Without the LCM, fraction addition requires multiplying denominators together and then simplifying — the LCM shortcut avoids that extra simplification step.
RSA Encryption Uses Co-prime Numbers
The RSA cryptographic algorithm — used in HTTPS, banking, and secure email — relies on choosing two large co-prime numbers. The security comes from the fact that while HCF(e, φ(n)) = 1 is easy to verify, recovering the factors of n from e and the public key is computationally infeasible. Every secure website you visit uses this principle.
Gear Ratios and LCM
In mechanical engineering, two meshing gears with tooth counts a and b will repeat the same pair of teeth engaging after LCM(a,b) rotations total. Engineers choose gear tooth counts to avoid repeated wear on the same teeth — which means deliberately choosing numbers with a high LCM (i.e. low HCF, ideally co-prime). This extends gear life significantly.
HCF Simplifies Ratios in Finance
Sharing profits in a ratio of 48:36:24 — find HCF(48,36,24) = 12, so the simplified ratio is 4:3:2. Interest calculations, mixture problems and investment allocations all reduce to finding HCF to simplify the underlying ratio. The "simplest form" of any ratio is found by dividing all terms by their HCF.
Music Theory and LCM
In music, polyrhythms occur when two rhythms with different beat counts play simultaneously. A 3-against-4 polyrhythm (triplet vs. quarter notes) repeats every LCM(3,4) = 12 subdivisions. West African drumming, jazz, and contemporary classical music all use polyrhythms whose period is an LCM. Every musician who plays in compound time is implicitly using LCM.
Computer Science: Memory Alignment
CPUs access memory most efficiently when data is aligned to multiples of its size. When you need a buffer that's accessible for two data structures of sizes a and b bytes, the alignment requirement is LCM(a,b). Compiler padding, struct layout, SIMD instruction alignment requirements — all solved with LCM arithmetic under the hood.
The LCM of 1 to n Grows Exponentially
LCM(1,2,3,...,n) grows roughly as e^n by the prime number theorem. LCM(1..10) = 2520. LCM(1..20) = 232,792,560. LCM(1..30) ≈ 2.3 × 10¹⁴. This exponential growth is related to why the harmonic series diverges and appears in estimates for the distribution of prime numbers — a deep connection between LCM and prime counting.
Frequently Asked Questions
Common questions about LCM, HCF, co-prime numbers, the Euclidean Algorithm and practical uses