An LCM and GCD calculator with prime factors and Euclid’s algorithm
This free LCM and GCD calculator finds the least common multiple and the greatest common divisor of two or more whole numbers at once. The GCD is the same thing as the HCF (highest common factor) taught in Indian and British schools, and the GCF (greatest common factor) used in many US textbooks.
Alongside the answers you get a prime factorisation table — the method most teachers ask for — and every line of Euclid’s algorithm, the fast method used by computers. All arithmetic uses arbitrary-precision integers, so 20-, 50- or 100-digit numbers give exact results.
How to use the LCM and GCD Calculator
- Type two or more whole numbers into the box, separated by commas or spaces — for example 12, 18, 30.
- Read the GCD (HCF) and the LCM in the two result panels; they update as you type.
- Look at the prime factorisation table: each column is a prime, and the last two rows show which powers make up the GCD and the LCM.
- Follow Euclid’s algorithm below the table to see the divisions that lead to the GCD, and how each LCM is built from it.
- Press “Copy results” to paste both answers into your notes.
LCM and GCD Calculator features
Any number of integers
Works with 2 to 50 numbers; the GCD and LCM are combined pair by pair, with every pair shown.
Prime factor table
Shows each number’s prime powers side by side, with the GCD (lowest powers) and LCM (highest powers) rows.
Euclid’s algorithm
Each division with its quotient and remainder, the way it is set out in textbooks.
Exact big numbers
BigInt arithmetic and a Pollard rho factoriser handle numbers far beyond a normal calculator’s 15 digits.
Sensible edge cases
Negative numbers use their absolute value, zeros are explained, and coprime numbers are flagged.
Three ways to find the GCD and LCM
1. Listing. For small numbers, list the factors (for the GCD) or the multiples (for the LCM) and pick the largest shared factor or the smallest shared multiple. Factors of 12: 1, 2, 3, 4, 6, 12; of 18: 1, 2, 3, 6, 9, 18 — so the GCD is 6. Multiples of 12: 12, 24, 36…; of 18: 18, 36… — so the LCM is 36.
2. Prime factorisation. Write each number as a product of primes. The GCD multiplies the primes common to all numbers, each to its lowest power; the LCM multiplies every prime that appears, each to its highest power. For 12 = 2² × 3 and 18 = 2 × 3², GCD = 2 × 3 = 6 and LCM = 2² × 3² = 36.
3. Euclid’s algorithm. Divide the larger number by the smaller and replace the pair with (smaller, remainder) until the remainder is 0. For 252 and 105: 252 = 2 × 105 + 42, 105 = 2 × 42 + 21, 42 = 2 × 21 + 0, so the GCD is 21. It needs no factorising, which is why it stays fast for huge numbers.
For two numbers, the results are linked: GCD × LCM = a × b. So LCM(252, 105) = 252 × 105 ÷ 21 = 1,260.
Where the LCM and GCD are used
- Adding fractions: the lowest common denominator of 5/12 and 7/18 is LCM(12, 18) = 36. The Fraction Calculator uses exactly this step.
- Simplifying: dividing 84/126 by GCD(84, 126) = 42 gives 2/3 in one move; the same works for ratios in the Ratio Calculator.
- Timetables: buses leaving every 12 and 18 minutes depart together again after LCM(12, 18) = 36 minutes.
- Tiling and cutting: the largest square tile that fits a 240 cm × 180 cm floor exactly is GCD(240, 180) = 60 cm, so you need 4 × 3 = 12 tiles.
- Sharing equally: 48 pencils and 36 erasers can be packed into at most GCD = 12 identical kits of 4 pencils and 3 erasers.
LCM and GCD Calculator FAQ
What is the difference between LCM and GCD?
The GCD is the largest number that divides all your numbers exactly; the LCM is the smallest number that all of them divide into. For 8 and 12, the GCD is 4 and the LCM is 24. The GCD can never be larger than the smallest number, and the LCM can never be smaller than the largest.
Is HCF the same as GCD?
Yes. Highest common factor (HCF), greatest common divisor (GCD) and greatest common factor (GCF) are three names for the same thing. This LCM and GCD calculator gives one answer that covers all three.
How do I find the LCM of three or more numbers?
Work in pairs: LCM(a, b, c) = LCM(LCM(a, b), c). For 4, 6 and 10: LCM(4, 6) = 12, then LCM(12, 10) = 60. The calculator shows each pair in the working.
What does it mean if the GCD is 1?
The numbers are coprime (relatively prime): they share no prime factor. Two different primes are always coprime, but so are non-primes such as 8 and 15.
Can I find the GCD of very large numbers?
Yes. Euclid’s algorithm needs only divisions, so even 100-digit numbers take a handful of steps. Prime factorisation of huge numbers is much harder; if a factor can’t be split quickly, the table shows it in brackets while the GCD and LCM stay exact. To test a single number, use the Prime Number Checker.
What are the GCD and LCM when one number is 0?
GCD(0, n) = n, because every number divides 0. The LCM involving 0 is 0, since 0 is the only common multiple. The calculator notes this when a zero is entered.