Skip to the tool
CALCPARK

GCD and LCM Calculator

Find the greatest common divisor (GCF/HCF) and least common multiple of 2 to 10 numbers, with Euclid’s algorithm written out and the prime factorisation of each number.

Calculated on your device
Loading the tool…

How to use it

  1. Type 2 to 10 whole numbers separated by commas, spaces or new lines. Negative numbers are treated by their absolute value; 0 is rejected.
  2. Read the GCD and LCM; for two numbers the gcd × lcm check is shown.
  3. Follow Euclid’s steps for each pair – the algorithm is chained, gcd(a, b) first, then gcd(result, c), and so on.
  4. Compare with the prime factorisation of every number and the GCD/LCM written as products of primes.
  5. Copy the result or the link.

Example

12, 18 and 30: gcd(12, 18): 18 = 1 × 12 + 6, 12 = 2 × 6 + 0 → 6. Then gcd(6, 30): 30 = 5 × 6 + 0 → 6. LCM: lcm(12, 18) = 12 × 18 ÷ 6 = 36, lcm(36, 30) = 36 × 30 ÷ 6 = 180. By primes: 12 = 2² × 3, 18 = 2 × 3², 30 = 2 × 3 × 5, so gcd = 2 × 3 = 6 and lcm = 2² × 3² × 5 = 180.

Algorithms

Euclid:  gcd(a, b) = gcd(b, a mod b),  gcd(a, 0) = a
several: gcd(a, b, c, …) = gcd(gcd(a, b), c, …);  lcm likewise
lcm(a, b) = |a · b| / gcd(a, b)
primes:  gcd = ∏ p^min(eᵢ),  lcm = ∏ p^max(eᵢ)

All arithmetic uses arbitrary-precision integers, so the GCD and LCM are exact for numbers of any length – the Euclidean algorithm needs at most about 5 × (number of digits) divisions. Prime factorisation is by trial division and is only attempted for numbers up to 10¹⁵ (it is fast there because every prime factor except possibly one is below 31.6 million); larger inputs are reported as “too large to factorise” while the GCD and LCM remain exact. The GCD of a set containing 0 is left undefined here, although mathematically gcd(a, 0) = a.

Sources: Euclid, Elements, Book VII, Propositions 1–2, Wolfram MathWorld – Greatest common divisor.

Questions

What is the difference between GCD, GCF and HCF?
Nothing – greatest common divisor, greatest common factor and highest common factor are three names for the same number. GCF is common in US schools, HCF in the UK and India.
Why do I need the LCM?
To add fractions (the common denominator), to find when repeating events coincide (buses every 12 and 18 minutes meet every 36 minutes) and in gear and calendar problems.
Does the order of the numbers matter?
No. The GCD and LCM are the same in any order; only the chain of Euclid steps shown changes.