Procedure
HCF from prime factors: keep only the primes both numbers share
Quantitative Aptitude • Number System
Statement
The HCF (highest common factor) is the largest number that divides both. Every common factor is built from primes that appear in both numbers. So write each number as a product of primes; the HCF is the product of the shared primes, each with the smaller of its two counts. If no prime is shared, the HCF is 1.
How to use it
- 1Break each number into primes.
- 2Mark the primes that appear in both, with the smaller count of each.
- 3Multiply the marked primes. If none is shared, the HCF is 1.
Worked example
Find the HCF of 84 and 90.
Step-by-step
- 1and .
- 2Shared: one 2 and one 3.
Why: 84 has two 2s but 90 has only one, so only one 2 is shared.
- 3HCF .
Answer
6
Watch out
Taking a prime as many times as it appears in the bigger count gives too large an answer; multiplying all the primes gives the LCM, not the HCF.