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

List all factors of each number. Find the common factors. Pick the largest.

GCF(18, 24) by listing

Factors of 18: 1, 2, 3, 6, 9, 18

Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24

Common: 1, 2, 3, 6 → GCF = 6

Method 2 – Prime Factorization

Write each number as a product of primes. Multiply the primes that appear in both factorizations (using the lowest power).

GCF(36, 48) by prime factorization

36 = 2² × 3² 48 = 2⁴ × 3

Common prime factors: 2 (lowest power = 2²) and 3 (lowest power = 3¹)

GCF = 2² × 3 = 4 × 3 = 12

Method 3 – Ladder (Division) Method

Divide both numbers by any common prime. Keep dividing until no common factor remains. Multiply all the divisors.

GCF(60, 90) by ladder method

Both even → divide by 2: 30, 45. Both divisible by 3: 10, 15. Both divisible by 5: 2, 3. No common factor left.

GCF = 2 × 3 × 5 = 30

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.

Practice: Try a Method

Find the GCF