HCF Using Prime Factors

Introduction

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

12

The Method: Shared Primes at Their Lowest Powers

1

Worked Example: HCF of 36 and 48

36 = 2^2 \times 3^2

Prime	Power in $36$	Power in $48$	Lowest power
$2$	$2$	$4$	$2$
$3$	$2$	$1$	$1$

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

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 = 2^2 \times 3 \times 5

90 = 2 \times 3^2 \times 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$

\text{HCF}(60, 90) = 2 \times 3 \times 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 $2^2$ in $60$ and as $2^1$ in $90$ . If we tried to include $2^2$ in the HCF, the result would contain a factor of $4$ . But $90$ is not divisible by $4$ , so a number containing $2^2$ 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 = 2^3 \times 3

36 = 2^2 \times 3^2

60 = 2^2 \times 3 \times 5

Venn diagram showing prime factors of 24, 36, and 60 with shared factors in the central region

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:

\text{HCF}(24, 36, 60) = 2^2 \times 3 = 4 \times 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 = 2^3 \times 3 \times 7

252 = 2^2 \times 3^2 \times 7

The shared primes are $2$ , $3$ , and $7$ , taken at powers $2$ , $1$ , and $1$ respectively:

\text{HCF}(168, 252) = 2^2 \times 3 \times 7 = 4 \times 3 \times 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.

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.

Prime

Power in

60

Power in

90

Lowest power

2

2

1

1

3

1

2

1

5

1

1

1

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

—

Introduction

From Factor Lists to Prime Factors

The Method: Shared Primes at Their Lowest Powers

Worked Example: HCF of 36 and 48

Join the 1M+ learners on CodeSignal

Why Only Shared Primes Count

Why the Lowest Power?

Extending to Three Numbers

When This Method Really Shines

Conclusion and Next Steps