HCF by Prime Factorization: Method, Rules and Examples

HCF by Prime Factorization is found by writing each number as a product of prime numbers and multiplying the common prime factors with their smallest powers. This page explains the factorization method for two or more numbers, including repeated prime factors, the HCF of numbers with no common prime factor, and solved numerical examples.

On this page

What Is HCF by Prime Factorization?

HCF by Prime Factorization is the method of finding the highest common factor by comparing the prime factors of the given numbers. The HCF is the product of every common prime factor raised to the smallest power appearing in the factorizations.

For example, 72 = 2³ × 3² and 120 = 2³ × 3 × 5. The common prime factors are 2 and 3. Their smallest powers are 2¹? Wait, 2 powers are 3 and 3, so smallest is 2³; 3 powers are 2 and 1, so smallest is 3¹. Therefore, HCF = 2³ × 3 = 24.

HCF by Prime Factorization Formula & Tricks

Important Formulas

HCF using prime powers
HCF = product of common prime factors with their smallest exponents

If a prime p has powers pᵃ, pᵇ and so on in the numbers, use p raised to the minimum exponent among them.

Two-number form
HCF(a, b) = ∏ pᵐ, where m = min(exponents of p in a and b)

Factor both numbers, identify common primes, and multiply each common prime using its lower power.

Quick Tricks

Choose the lowest power of each common prime

Do not add the powers of common primes. Select the smallest exponent for each prime that occurs in every number.

Example: For 180 = 2² × 3² × 5 and 252 = 2² × 3² × 7, use 2² and 3². HCF = 2² × 3² = 36.
No common prime factor means HCF is 1

If the prime factorizations share no prime factor, the numbers are co-prime and their HCF is 1.

Example: 35 = 5 × 7 and 64 = 2⁶ share no prime factor, so HCF = 1.
The HCF cannot contain a prime absent from any number

A prime factor is included only when it appears in every given number. A prime appearing in just one number is excluded.

Example: For 72 = 2³ × 3² and 125 = 5³, there is no common prime factor, so HCF = 1.

HCF by Prime Factorization Concepts

Steps in the Prime Factorization Method

To find the HCF, factor every number into primes, identify the primes common to all numbers, select their lowest powers, and multiply them.

The procedure is: (1) write the prime factorization of each number; (2) compare the prime factors; (3) retain only factors present in every number; (4) use the smallest exponent of each retained factor; and (5) multiply the selected factors.

Example: 84 = 2² × 3 × 7 and 126 = 2 × 3² × 7. The selected factors are 2¹, 3¹ and 7¹, so HCF = 2 × 3 × 7 = 42.

Handling Repeated Prime Factors

When a prime factor occurs with different powers, the HCF contains that prime with the smallest power.

For example, if one number contains 2⁴ and another contains 2², the HCF can contain only 2² from this prime. The same comparison is made separately for every common prime.

Example: 96 = 2⁵ × 3 and 144 = 2⁴ × 3². HCF = 2⁴ × 3 = 48.

HCF of Three or More Numbers

For three or more numbers, retain only the prime factors common to all numbers and choose the smallest exponent across all factorizations.

A prime that is missing from even one number cannot be part of the HCF. For each prime present in every number, compare all its exponents and use the minimum.

Example: 72 = 2³ × 3², 90 = 2 × 3² × 5 and 120 = 2³ × 3 × 5. Common factors with minimum powers are 2¹ and 3¹, so HCF = 6.

Special Case: 1 and Co-Prime Numbers

The HCF of 1 and any positive integer is 1, and two numbers with no common prime factor also have HCF 1.

The number 1 has no prime factorization into prime numbers. Thus, no prime factor can be selected from a pair containing 1. Similarly, numbers such as 35 and 64 have no common prime factor and are co-prime.

Example: HCF(1, 48) = 1. Also, 18 = 2 × 3² and 25 = 5² share no prime factor, so HCF(18, 25) = 1.

HCF by Prime Factorization Video Lessons

Watch short topic-wise lessons for quick revision.

14 Lessons
Lesson 1 of 14 Quick Revision

HCF Using Prime Factorisation and Euclidean Algorithm

Learn to calculate the Highest Common Factor using prime factorisation and the Euclidean algorithm, with a clear understanding of how both methods work.

Continue with more lessons and practice in PrepShots.Watch More in App - Start ₹1 Trial →
More HCF by Prime Factorization Lessons Scroll to explore →

Practice HCF by Prime Factorization Questions

Practise published questions related to this topic.

1The sum of a positive number and its square is 90. What is the value of the number?→ 2Find the smallest digit x such that the 6-digit number 28x219 is divisible by both 9 and 11.→ 3There are 156 boy students and 143 girl students in a school. The principal wants to divide them in sections, such that a section can have only boys or only girls. If all sections should have the same number of students, and the principal wants to have as fewer sections as possible, how many sections would be there in the school?→ 4Find the LCM of the numbers 780, 2080 and 2600.→ 5The greatest possible length (in cm) which can be used to measure exactly the lengths 6 metres, 2 metres 70 cm, 11 metres 20 cm is ______.→ 6The sum of a number and its positive square root is 56. What is the value of square of the number?→ 7Find the least number that must be added to 5600 to make it a perfect square.→ 8What is the smallest 5-digit number that is exactly divisible by 12, 15 and 20?→ 9What is the square root of 4096?→ 10Find the square root of 64009.→

HCF by Prime Factorization Quick Quiz

Attempt 5 questions and check your score instantly.

Quick Revision Notes

HCF by Prime Factorization: Quick Revision

Use prime factorizations to select common primes with their minimum powers.

  • Prime-factorize every given number completely.
  • Only prime factors present in every number can be included in the HCF.
  • Use the smallest exponent of each common prime factor.
  • Multiply the selected prime powers to obtain the HCF.
  • If there is no common prime factor, the HCF is 1.
  • The HCF of 1 and any positive integer is 1.
  • For 72 and 120, use 2³ and 3¹, giving HCF = 24.

HCF by Prime Factorization FAQs

What is the formula for HCF by prime factorization?

HCF = product of common prime factors raised to their smallest exponents. In symbols, HCF(a, b) = ∏p^min(exponents of p in a and b).

How do you find the HCF of 60 and 84 by prime factorization?

60 = 2² × 3 × 5 and 84 = 2² × 3 × 7. Therefore, HCF = 2² × 3 = 12.

Why are the smallest powers used in HCF?

The HCF must divide every given number. A common prime can occur only up to the lowest exponent present in any one of the numbers.

What is the HCF of 48, 72 and 120?

48 = 2⁴ × 3, 72 = 2³ × 3² and 120 = 2³ × 3 × 5. The common minimum powers are 2³ and 3, so HCF = 24.

What happens if one prime factor occurs in only two of three numbers?

It is excluded because an HCF factor must divide all the numbers. For example, 5 is excluded from the HCF of 60, 75 and 84 because 5 is not a factor of 84.

Can the HCF be greater than the smallest given number?

No. The HCF is a factor of every given number, so it cannot exceed the smallest number. For example, HCF(18, 30) = 6, which is less than 18.

Continue learning HCF by Prime Factorization on PrepShots

Continue on PrepShots