How do you find the HCF using prime factorization?

To find the HCF by prime factorization: (1) Break each number into its prime factors. For example, 36 = 2² × 3² and 48 = 2⁴ × 3. (2) Identify the prime factors common to all numbers — here 2 and 3. (3) Take the lowest power of each common prime: 2² (min of 2, 4) and 3¹ (min of 2, 1). (4) Multiply: HCF = 2² × 3 = 12.

What is the difference between HCF and LCM?

HCF (Highest Common Factor) is the largest number that divides into all given numbers. LCM (Least Common Multiple) is the smallest number that all given numbers divide into. For 12 and 18: HCF = 6 (the biggest factor they share), LCM = 36 (the smallest multiple they share). They are related by the formula: HCF(a, b) × LCM(a, b) = a × b.

How do you find the HCF of three or more numbers?

To find the HCF of three or more numbers, apply the HCF function iteratively: HCF(a, b, c) = HCF(HCF(a, b), c). For example, HCF(24, 36, 60): first find HCF(24, 36) = 12, then HCF(12, 60) = 12. Alternatively, prime-factorize all numbers and take the lowest power of every prime that appears in all factorizations. This calculator supports up to 10 numbers.

What are coprime numbers?

Two numbers are coprime (or relatively prime) when their HCF is 1, meaning they share no common prime factors. For example, 8 and 15 are coprime because the factors of 8 (1, 2, 4, 8) and 15 (1, 3, 5, 15) share only 1. Coprime numbers don't need to be prime themselves — 9 and 14 are coprime even though neither is prime.

What is the HCF of 24 and 36?

The HCF of 24 and 36 is 12. By prime factorization: 24 = 2³ × 3 and 36 = 2² × 3². The common primes are 2 and 3. Taking the lowest powers: 2² and 3¹. So HCF = 2² × 3 = 4 × 3 = 12. You can verify: 24 ÷ 12 = 2 and 36 ÷ 12 = 3, both whole numbers.

Why is HCF used for simplifying fractions?

The HCF tells you the largest number you can divide both the numerator and denominator by to reduce a fraction to its simplest form. To simplify 18/24: find HCF(18, 24) = 6, then divide both by 6 to get 3/4. This works because dividing numerator and denominator by their HCF removes all shared factors, leaving the fraction in lowest terms.

Can the HCF be larger than one of the numbers?

No. The HCF of any set of positive integers is always less than or equal to the smallest number in the set. This is because a factor of a number cannot exceed the number itself. The HCF equals the smallest number only when the smaller number divides evenly into all the other numbers. For example, HCF(6, 12) = 6.

What is the HCF of two consecutive numbers?

The HCF of any two consecutive numbers is always 1. Consecutive numbers are always coprime because they cannot share any prime factor — if a prime p divided both n and n+1, it would also divide their difference (n+1) − n = 1, which is impossible. For example, HCF(14, 15) = 1 and HCF(99, 100) = 1.

HCF Calculator

Numbers

Enter at least 2 positive integers to find their HCF.

HCF of 12, 18

LCM = 36

HCF × LCM = 216

Summary

HCF and LCM for 12, 18

HCF (GCD)

LCM

Numbers

12, 18

Count

HCF × LCM = 6 × 36 = 216 = 12 × 18 ✓

Prime Factorization Method

Find the prime factorization of each number, then take the lowest power of each common prime

1Find the prime factorization of each number

12 = 2² × 3

18 = 2 × 3²

2Take the lowest power of each common prime factor

Prime	12	18	Min
2	2	1	1
3	1	2	1

3Multiply the lowest powers together

HCF = 2 × 3

HCF = 6

Euclidean Algorithm

Repeatedly divide the larger number by the smaller until the remainder is 0

118 = 1 × 12 + 6

212 = 2 × 6 + 0

The last non-zero remainder is the HCF

HCF = 6

Listing Factors Method

List all factors of each number and find the largest common one

Factors of 12:

1234612

Factors of 18:

1236918

The largest factor common to all numbers

HCF = 6

Related Information

Properties and relationships

HCF (GCD):HCF(12, 18) = 6

LCM:LCM(12, 18) = 36

HCF factorized:6 = 2 × 3

Relationship:HCF × LCM = 12 × 18 = 216

Coprime?:No — they share common factor(s)

What Is the HCF (Highest Common Factor)?

Understanding HCF, GCD, and GCF — they all mean the same thing

HCF

Highest Common Factor

Largest number dividing all inputs

= GCD = GCF

Same concept

Different names, identical result

O(log n)

Euclidean

Efficient even for large numbers

The Highest Common Factor (HCF) of two or more integers is the largest positive integer that divides each of those numbers without leaving a remainder. It is also known as the Greatest Common Divisor (GCD) or Greatest Common Factor (GCF). For example, the HCF of 12 and 18 is 6, because 6 is the largest number that divides both evenly.

HCF-LCM relationship

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

Holds for any two positive integers

For any two positive integers, the product of their HCF and LCM equals the product of the numbers themselves. This identity provides an efficient way to compute the LCM when the HCF is known: LCM(a, b) = (a × b) / HCF(a, b).

Three Methods to Find the HCF

Choose the method that suits your numbers

Prime factorization

Take min power of each common prime

Best for understanding

Euclidean algorithm

HCF(a, b) = HCF(b, a mod b)

Fastest for large numbers

Listing factors

List all factors, pick the largest common one

Simplest for small numbers

Worked example — HCF(36, 48)

Number A

2² × 3²

Number B

2⁴ × 3

Common

2² × 3¹

min powers

HCF

result

36 = 2² × 3² and 48 = 2&sup4; × 3. The common primes are 2 and 3. Taking the lowest power of each: 2² × 3¹ = 4 × 3 = 12.

The Euclidean Algorithm Step by Step

The fastest method — described by Euclid around 300 BCE

The Euclidean Algorithm finds the HCF by repeatedly dividing the larger number by the smaller and taking the remainder, until the remainder is 0. The last non-zero remainder is the HCF.

Example: HCF(48, 18)

148 = 2 × 18 + 12

218 = 1 × 12 + 6

312 = 2 × 6 + 0

HCF(48, 18) = 6

Time complexity

O(log(min(a, b)))

Worst case

Consecutive Fibonacci numbers

Common HCF Values Reference

Quick-reference table for frequently searched pairs

Numbers	HCF	LCM	Coprime?
12, 18	6	36	No
24, 36	12	72	No
15, 20	5	60	No
8, 12	4	24	No
14, 21	7	42	No
30, 54	6	270	No
7, 13	1	91	Yes
36, 48, 60	12	720	No

Real-World Applications of HCF

Where HCF is used in everyday life and mathematics

Simplifying Fractions

To simplify 18/24, find HCF(18, 24) = 6. Divide both by 6: 18/24 = 3/4. The HCF gives the largest number to divide by for the lowest terms.

Dividing Into Equal Groups

24 red tiles and 36 blue tiles — the most identical groups you can make is HCF(24, 36) = 12. Each group gets 2 red and 3 blue tiles.

Tiling & Flooring

A 12 m × 18 m room — the largest square tile that fits perfectly is HCF(12, 18) = 6 m per side. You need (12/6) × (18/6) = 6 tiles.

Cryptography (RSA)

RSA encryption verifies that keys are coprime using GCD. Efficient HCF calculation is fundamental to modern public-key cryptography.

Common Mistakes to Avoid

Pitfalls that trip up students when finding HCF

Confusing HCF with LCM

HCF is the largest common factor; LCM is the smallest common multiple. For 12 and 18: HCF = 6, LCM = 36. They are opposite operations — HCF divides into both, LCM is divisible by both.

Using highest power instead of lowest

In prime factorization, HCF takes the lowest power of each common prime. Taking the highest gives you the LCM instead. For 12 = 2²×3 and 18 = 2×3²: HCF uses 2¹ and 3¹, not 2² and 3².

Including non-common primes

The HCF only uses primes present in all factorizations. If 15 = 3 × 5 and 10 = 2 × 5, the only common prime is 5. Factor 3 doesn't appear in 10, so HCF = 5 (not 15).

Multiplying the numbers directly

The product of two numbers is not their HCF. 12 × 18 = 216, but HCF(12, 18) = 6. The HCF is always ≤ the smallest input number.

Pro Tips

Get the most out of this calculator

Use the HCF-LCM shortcut

If you already know HCF(a, b), compute LCM instantly: LCM = (a × b) / HCF. No need to factorize again.

Consecutive numbers are coprime

Any two consecutive integers always have HCF = 1. Quick check: if your numbers differ by 1, no calculation needed.

Simplify fractions in one step

Divide both numerator and denominator by their HCF to instantly reduce any fraction to lowest terms.

Frequently Asked Questions

Common questions about HCF, GCD, and finding common factors

To find the HCF using the Euclidean division method: (1) Divide the larger number by the smaller and note the remainder. (2) Replace the larger number with the smaller, and the smaller with the remainder. (3) Repeat until the remainder is 0. The last non-zero remainder is the HCF. For example, HCF(48, 18): 48 ÷ 18 = 2 remainder 12, then 18 ÷ 12 = 1 remainder 6, then 12 ÷ 6 = 2 remainder 0. So HCF = 6.

Embed HCF Calculator

Add this calculator to your website or blog for free.

Related calculators from other categories

Last updated May 2, 2026

HCF Calculator

Summary

Prime Factorization Method

1Find the prime factorization of each number

2Take the lowest power of each common prime factor

3Multiply the lowest powers together

Euclidean Algorithm

Listing Factors Method

Factors of 12:

Factors of 18:

Related Information

What Is the HCF (Highest Common Factor)?

Three Methods to Find the HCF

The Euclidean Algorithm Step by Step

Common HCF Values Reference

Real-World Applications of HCF

Simplifying Fractions

Dividing Into Equal Groups

Tiling & Flooring

Cryptography (RSA)

Common Mistakes to Avoid

Pro Tips

Frequently Asked Questions

Embed HCF Calculator

You Might Also Like