Factors, Multiples & Primes
Methods for Finding the GCF / HCF
There are three common methods for finding the GCF. The best choice depends on the size of the numbers and how quickly you need the answer.
Choosing the right method is not just a classroom exercise — it mirrors a real trade-off computer scientists face constantly. Listing factors is easy to explain but hopelessly slow for large numbers; prime factorization is elegant, but factoring very large numbers is itself famously hard (the security of RSA encryption, which protects much of the internet, relies on exactly how hard it is). The ladder method sidesteps factoring entirely by using repeated division instead — which is why it, in the more general form called the Euclidean Algorithm, is the method real software actually uses to compute GCFs of enormous numbers in a fraction of a second.
Method 1 – Listing Factors
This is the most direct method of the three — it doesn’t need any prime knowledge at all, which makes it the natural starting point when you’re first learning about the GCF. The trade-off is that it gets slow and error-prone once the numbers get bigger, which is exactly why Methods 2 and 3 exist.
Step by Step
- List every factor of the first number, from smallest (1) to largest (the number itself).
- List every factor of the second number the same way.
- Compare the two lists and pick out every number that appears in both — these are the common factors.
- The largest number in that common list is the GCF.
Factors of 18: 1, 2, 3, 6, 9, 18
Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24
Common factors: 1, 2, 3, 6 — the largest is 6.
Factors of 48 (using the factor-pair trick up to √48≈6.9): 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
Factors of 60 (using the factor-pair trick up to √60≈7.7): 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
Common factors: 1, 2, 3, 4, 6, 12 — the largest is 12.
Notice how much longer both lists already are with numbers this size — that growing effort is exactly why Methods 2 and 3, below, become the more practical choice as numbers get larger.
Method 2 – Prime Factorization
Instead of listing every factor, this method breaks each number down into its prime building blocks, then compares those. It scales far better than listing factors, and it’s especially efficient once you need the GCF of three or more numbers at once.
Step by Step
- Find the prime factorization of each number — use a factor tree or repeated division by small primes (2, 3, 5, 7…) until only primes remain.
- Write each factorization in exponent form (e.g. 2² × 3³).
- Identify every prime that appears in both factorizations — ignore any prime that only shows up in one of them.
- For each shared prime, take whichever exponent is lower (smaller) between the two numbers.
- Multiply those lower powers together — the result is the GCF.
36 = 2² × 3² 48 = 2⁴ × 3¹
| Prime | In 36 | In 48 | Lower power used |
|---|---|---|---|
| 2 | 2² | 2⁴ | 2² |
| 3 | 3² | 3¹ | 3¹ |
84 = 2² × 3¹ × 7¹ 90 = 2¹ × 3² × 5¹
| Prime | In 84 | In 90 | In both? | Used in GCF |
|---|---|---|---|---|
| 2 | 2² | 2¹ | Yes | 2¹ (lower power) |
| 3 | 3¹ | 3² | Yes | 3¹ (lower power) |
| 5 | — | 5¹ | No — only in 90 | excluded |
| 7 | 7¹ | — | No — only in 84 | excluded |
Even though 84 and 90 both have plenty of prime factors, only 2 and 3 appear in both lists — 7 belongs to 84 alone and 5 belongs to 90 alone, so neither one contributes to the GCF at all.
Method 3 – Ladder (Division) Method
The ladder method (sometimes called the “cake method” or “staircase method”) finds the GCF by repeatedly dividing both numbers by the same small prime, one step at a time, instead of factoring each number separately first. Every division you perform becomes one “rung” of the ladder, written underneath the last, until the two numbers left at the bottom have nothing left in common. It is faster to do by hand than full prime factorization for most textbook-sized numbers, because you only ever divide by small primes, one at a time, and you can stop the moment there is nothing left to share.
How to Build the Ladder, Step by Step
- Write the two numbers side by side at the top — this is the top of the ladder.
- Find the smallest prime number that divides both numbers exactly. Always test in increasing order: 2 first, then 3, then 5, then 7, and so on — never skip ahead.
- Write that prime in a column on the left of the ladder. Divide both numbers by it, and write the two answers directly underneath, starting a new rung.
- Look at the new pair of numbers on this rung. Repeat step 2 — find the smallest prime that divides both of them. It might be the same prime as before (use it again!), or it might be the next one up.
- Keep adding rungs until the pair of numbers at the very bottom share no common factor at all — in other words, until they are coprime (their own GCF is 1). That is your signal to stop.
- Multiply every divisor written down the left-hand side of the ladder. That product is the GCF of the two original numbers.
| Prime | Quick divisibility check |
|---|---|
| 2 | The number is even (ends in 0, 2, 4, 6 or 8). |
| 3 | The digits add up to a multiple of 3. |
| 5 | The number ends in 0 or 5. |
| 7, 11, 13… | No simple shortcut — just try dividing; if it comes out exact, it works. |
Worked Example 1 — GCF(60, 90)
Start with 60 and 90 at the top. Test 2 first: both are even, so 2 becomes the first rung.
| Divide by | 60 | 90 |
|---|---|---|
| 2 | 30 | 45 |
| 3 | 10 | 15 |
| 5 | 2 | 3 |
2 and 3 share no common factor other than 1 — the ladder stops here.
Reading each rung: 60 and 90 are both even, so divide by 2 to get 30 and 45. Both of those are divisible by 3, so divide by 3 to get 10 and 15. Both of those are divisible by 5, so divide by 5 to get 2 and 3 — and since 2 and 3 have nothing left in common, the ladder is complete. Multiplying the three divisors used, 2 × 3 × 5, gives the GCF: 30.
Worked Example 2 — GCF(72, 120), Reusing the Same Prime
This example shows what happens when the same small prime works more than once in a row before you need to move on to the next one.
| Divide by | 72 | 120 |
|---|---|---|
| 2 | 36 | 60 |
| 2 | 18 | 30 |
| 2 | 9 | 15 |
| 3 | 3 | 5 |
3 and 5 share no common factor other than 1 — the ladder stops here.
Here, 2 divides both numbers three rungs in a row (72→36→18→9 and 120→60→30→15), because both original numbers contain 2³ as a factor. Once 9 and 15 are reached, 2 no longer divides 9 (it’s odd), so the ladder moves on to the next prime, 3, which divides both 9 and 15 exactly. That leaves 3 and 5 — two numbers with no shared factor — so the ladder is finished. Multiplying every divisor used, 2 × 2 × 2 × 3, gives the GCF: 24.
Method Comparison
| Method | Best For | Speed |
|---|---|---|
| Listing factors | Small numbers | Slow for large numbers |
| Prime factorization | Medium numbers, multiple numbers | Moderate |
| Ladder/Euclidean | Large numbers, two numbers | Fastest |
Key Takeaways
- All three methods give the same answer — choose based on the numbers.
- Prime factorization is great when you already need the factorization.
- The ladder method is the most efficient for large numbers.