Skip to main content
Sarkari.tools61 calculators for India

HCF and LCM Calculator

Calculate Highest Common Factor (HCF / GCD) and Least Common Multiple (LCM) for multiple numbers with prime factorization.

HCF (greatest common divisor)
12
LCM (least common multiple)
72

Working

Euclidean algorithm:

HCF(24, 36) = 12

Prime factorisation:

24 = 2^3 × 3

36 = 2^2 × 3^2

Check: HCF × LCM = 12 × 72 = 864 = 24 × 36

HCF and LCM Calculator: how it works

The Euclidean algorithm finds the highest common factor in a handful of steps, and the LCM follows from it directly.

The Euclidean algorithm

Repeatedly replace the larger number with the remainder of dividing it by the smaller. When the remainder reaches zero, the last non-zero value is the HCF.

Worked example · HCF of 24 and 36

Given

  • a = 36, b = 24

Working

  1. 136 ÷ 24 = 1 remainder 12
  2. 224 ÷ 12 = 2 remainder 0
  3. 3Last non-zero remainder is 12

HCF(24, 36) = 12

LCM from HCF

LCM(a, b) = (a × b) ÷ HCF(a, b)

Valid for two numbers only

Worked example · LCM of 24 and 36

Given

  • HCF = 12

Working

  1. 1LCM = (24 × 36) ÷ 12
  2. 2= 864 ÷ 12

LCM(24, 36) = 72

Prime factorisation

The alternative method: express each number as a product of primes, then take the lowest power of each shared prime for the HCF and the highest power of every prime for the LCM.

Worked example · Same numbers by factorisation

Given

  • 24 = 2³ × 3
  • 36 = 2² × 3²

Working

  1. 1HCF = 2² × 3¹ = 12 (lowest powers)
  2. 2LCM = 2³ × 3² = 72 (highest powers)

Same answers, different route

Where these appear

  • HCF: dividing quantities into the largest equal groups, simplifying fractions.
  • LCM: finding when repeating events coincide, adding fractions with unlike denominators.
  • Both appear routinely in SSC, banking and railway aptitude papers.

Frequently asked questions

HCF is the largest number that divides all the given numbers exactly. LCM is the smallest number that all of them divide into exactly.

More in Academics & Competitive Exams