Welcome back to Finding the Highest Common Factor! You are now on Lesson 3 of 4 in this course, which means you have already built a solid foundation. In the first two lessons, we identified common factors by listing and comparing factor lists, then selected the greatest one to find the HCF. That approach is reliable, but it can get slow when numbers grow larger.
In this lesson, we will learn a more efficient route: finding the HCF directly from the prime factorizations of the numbers involved. If you completed the earlier course on breaking numbers into primes, those skills are about to pay off in a big way.
From Factor Lists to Prime Factors
The Method: Shared Primes at Their Lowest Powers
Worked Example: HCF of 36 and 48
Why Only Shared Primes Count
Why the Lowest Power?
Extending to Three Numbers
When This Method Really Shines
Conclusion and Next Steps
In this lesson, we learned how to find the HCF by comparing prime factorizations rather than full factor lists. The process comes down to three ideas: identify the primes shared by all numbers, take each shared prime at its lowest appearing power, and multiply. We also explored why primes found in only one factorization are left out and why higher powers of shared primes cannot be used, since including them would produce a number that no longer divides every value in the set.
Now it is time to put this method into practice! The upcoming exercises will walk you through guided fill-in-the-blank examples first, then challenge you with larger numbers and sets of three, so you can build real confidence with this powerful technique.
Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal
Listing every factor of a number works well for small values like 12 or 18. But imagine finding all the factors of 252 or 360 — the lists get long, and mistakes become easy to make.
Prime factorization gives us a shortcut because it breaks each number down to its basic building blocks. As you may recall from a previous course, every whole number greater than 1 has a unique prime factorization. Comparing those building blocks tells us exactly what two numbers have in common, without writing out every single factor. The core idea is simple: if a prime appears in both factorizations, it contributes to the HCF; if it appears in only one, it does not.
Here is the step-by-step process for finding the HCF using prime factorization:
Find the prime factorization of each number.
Identify the primes that appear in every factorization (the shared primes).
For each shared prime, take the lowest power that appears across the factorizations.
Multiply these together to get the HCF.
If no prime is shared at all, the HCF is simply 1. As we saw in the previous lesson, that just means the numbers are coprime.
Let's see the method in action. First, we write the prime factorizations:
36=22×3248=24×3
Now we compare prime by prime:
Prime
Power in 36
Power in 48
Lowest power
2
2
4
2
3
2
1
1
Both factorizations contain 2 and 3, so both primes are shared. We take 2 at its lowest power (22) and 3 at its lowest power (31), then multiply:
HCF(36,48)=22×3=4×3=12
You can verify this with factor lists if you like: the factors common to 36 and 48 are 1,2,3,4,6,12, and the greatest is indeed 12.
You might wonder why we ignore a prime that appears in only one factorization. The reason comes straight from the definition of "factor." For a number to divide both values evenly, every prime in that number must be present in both factorizations. A prime that is missing from one side simply cannot be part of any common factor.
Let's explore this with 60 and 90:
60=22×3×590=2×32×5
Here, the primes 2, 3, and 5 all appear in both factorizations, so each one contributes. Taking the lowest powers:
Prime
Power in 60
Power in 90
Lowest power
2
2
1
1
3
1
2
1
5
1
1
1
HCF(60,90)=2×3×5=30
It is also worth understanding why we pick the lowest power of each shared prime, not the highest. Look at the prime 2 in the example above: it appears as 22 in 60 and as 21 in 90. If we tried to include 22 in the HCF, the result would contain a factor of 4. But 90 is not divisible by 4, so a number containing 22 could not divide 90 evenly.
By choosing the lower power, we guarantee the HCF divides both numbers without a remainder. The lowest power is the most that both numbers can "afford" to share.
The method works the same way with three or more numbers. A prime must appear in all factorizations to be included, and we still take the lowest power across the entire set. Let's find the HCF of 24, 36, and 60:
24=23×336=22×3260=22×3×5
Prime
Power in 24
Power in 36
Power in 60
Shared?
Lowest power
2
3
2
2
Yes
2
3
1
2
1
Yes
1
5
—
—
1
No
—
The prime 5 appears only in the factorization of 60, so it is excluded. Multiplying the shared primes at their lowest powers gives us:
HCF(24,36,60)=22×3=4×3=12
Notice that adding a third number to the set kept the HCF the same or made it smaller compared to any pair, because each new factorization adds another filter.
For small numbers, listing factors and comparing them is perfectly fine. The prime factorization method shows its true strength with larger numbers, where full factor lists would be long and error-prone. Consider finding the HCF of 168 and 252:
168=23×3×7252=22×32×7
The shared primes are 2, 3, and 7, taken at powers 2, 1, and 1 respectively:
HCF(168,252)=22×3×7=4×3×7=84
We reached the answer in just a few lines — no need to list over a dozen factors for each number. Think about a scenario where a warehouse has 168 bottles of water and 252 bottles of juice and needs to pack them into the largest possible number of identical supply kits with no leftovers. The HCF tells us that 84 kits can be made, each containing 2 waters and 3 juices. The bigger the numbers, the more time this method saves.
