Find the Highest Common Factor (HCF) and LCM of any two numbers instantly — with the Euclidean algorithm explained step by step.
The HCF Calculator (Highest Common Factor Calculator) finds the largest positive integer that divides two or more numbers without leaving a remainder. HCF is also known as the Greatest Common Factor (GCF) or Greatest Common Divisor (GCD) in different countries. In India's school curriculum (CBSE, ICSE, and state boards), the term HCF is used from Class 5 through Class 10 and is one of the most fundamental topics in number theory.
This calculator instantly finds the HCF of any two numbers and also displays their LCM (Least Common Multiple) as a bonus, since both are typically taught together in Indian schools.
Why HCF Matters
- Simplifying fractions: To reduce a fraction to its lowest terms, divide both numerator and denominator by their HCF. For example, 12/18 → divide both by HCF(12,18) = 6 → 2/3.
- Finding common denominators: HCF helps identify relationships between denominators when adding fractions.
- Dividing things equally: If you have 24 apples and 36 oranges and want to make identical fruit baskets with no fruit left over, HCF(24,36) = 12 tells you can make 12 baskets with 2 apples and 3 oranges each.
- Competitive exams: HCF and LCM problems appear in every major Indian competitive exam — SSC, IBPS banking, CAT, RRB, and entrance exams. Understanding HCF is essential for solving these quickly.
The Euclidean Algorithm
The Euclidean algorithm is the most efficient method for finding HCF. It works by repeatedly replacing the larger number with the remainder when divided by the smaller number, until the remainder is zero. The last non-zero remainder is the HCF.
For HCF(48, 18):
- 48 = 2×18 + 12 → HCF(48,18) = HCF(18,12)
- 18 = 1×12 + 6 → HCF(18,12) = HCF(12,6)
- 12 = 2×6 + 0 → HCF = 6
This algorithm runs in O(log n) time, making it extremely fast even for very large numbers.
1. Enter Number 1: Type the first positive integer.
2. Enter Number 2: Type the second positive integer.
3. View Results: The calculator instantly shows the HCF using the Euclidean algorithm, and also displays the LCM as a bonus result.
Euclidean Algorithm for HCF:
HCF(a, b) = HCF(b, a mod b) — repeatedly apply until remainder = 0
The last non-zero value is the HCF.
LCM from HCF:
LCM(a, b) = (a × b) / HCF(a, b)
Example: HCF(36, 48)
- 48 mod 36 = 12 → HCF(36, 12)
- 36 mod 12 = 0 → HCF = 12
- LCM = (36 × 48) / 12 = 1728 / 12 = 144
Example 1: HCF(12, 18) → 12 mod 18 = 12; 18 mod 12 = 6; 12 mod 6 = 0 → HCF = 6. LCM = (12×18)/6 = 36.
Example 2: HCF(100, 75) → 100 mod 75 = 25; 75 mod 25 = 0 → HCF = 25. LCM = (100×75)/25 = 300.
Example 3: HCF(17, 13) → Both are prime and different, so HCF = 1 (co-prime numbers). LCM = 17×13 = 221.