The MathBlog GCF calculator quickly finds the Greatest Common Factor of two or more numbers using four distinct methods: basic factorization, prime factorization, the Euclidean algorithm, and upside-down division. Simply insert numbers in the form below and get detailed, step-by-step solutions, helping you save time and better understand the process behind each method.
GCF Calculator
Enter positive whole numbers below:
What is the Greatest Common Factor?
The GCF is the largest whole number that divides two or more numbers evenly, without leaving a remainder.
Also known as the Greatest Common Divisor (GCD) or the Highest Common Factor (HCF), the Greatest Common Factor (GCF) is important for simplifying fractions, factoring in algebra, or simplifying ratios to only mention a few. It helps in solving divisibility problems and is also used in certain algorithms, particularly in optimization and cryptography.
How to Find GCF?
There are several methods to determine the GCF, each with its own level of simplicity and depth. Some are straightforward, while others require more steps. Familiarizing yourself with each approach helps you choose the one that works best for you:
- Listing all factors,
- Prime factorization,
- The Euclidean algorithm, and
- Upside-down division.
The best part is that finding the GCF involves only basic math operations like subtraction, division, or multiplication.
List of factors
This method involves listing all the factors of each number, then identifying the largest factor common to both or all numbers. It’s simple but can be time-consuming for large numbers.
Let’s take an example. What is the Greatest Common Factor of 18, 24, and 54?
We start by calculating the factors of each number:
- Factors of 18:
1, 2, 3, 6, 9, 18 - Factors of 24:
1, 2, 3, 4, 6, 8, 12, 24 - Factors of 54:
1, 2, 3, 6, 9, 18, 27, 54
The common factors are: 1, 2, 3, 6.
That means gcf(18,24,54) = 6.
Prime factors
This approach involves breaking down each number into its prime factors. The GCF is then determined by multiplying the common prime factors between the numbers.
Let’s take an example. What is the Greatest Common Factor of 27, 108, and 54?
We start by calculating the prime factors of each number:
- Prime factors of 27 are:
3 × 3 × 3. - Prime factors of 108 are:
2 × 2 × 3 × 3 × 3. - Prime factors of 54 are:
2 × 3 × 3 × 3.
Now that we found the prime factors of each number, it’s clear that the common prime factors are: 3 × 3 × 3.
That means thhe gcf(27, 108, 54) = 27.
Euclidean Algorithm
This method uses repeated division. It works by dividing the larger number by the smaller one, then replacing the larger number with the remainder and repeating until the remainder is zero. The last non-zero divisor is the GCF.
Let’s take an example. What is the Greatest Common Factor of 120 and 200?
#1: Arrange numbers in ascending order: 12, 20.
Take the smallest number (12) as the divisor and divide each number by it to find the remainder.
- 20 ÷ 12 = 1 remainder 8
Form a new set with the divisor and non-zero remainders, removing any duplicates: 12, 8.
#2: Arrange numbers in ascending order: 8, 12.
Take the smallest number (8) as the divisor and divide each number by it to find the remainder.
- 12 ÷ 8 = 1 remainder 4
Form a new set with the divisor and non-zero remainders, removing any duplicates: 8, 4.
#3: Arrange numbers in ascending order: 4, 8.
Take the smallest number (4) as the divisor and divide each number by it to find the remainder.
- 8 ÷ 4 = 2 remainder 0
Form a new set with the divisor and non-zero remainders, removing any duplicates: 4.
STOP. There’s only one number remaining, which means the Greatest Common Factor is 4.
Upside-Down Division
Also known as the ladder method, it involves dividing all the numbers by common prime divisors in a step-by-step process until no more division is possible. The product of the common divisors is the GCF.
Let’s take an example. What is the Greatest Common Factor of 120, 270, 60, and 90?
We start by successively dividing the given numbers by common prime divisors.
| 120 | 270 | 60 | 90 | |
| 2 | 60 | 135 | 30 | 45 |
| 3 | 20 | 45 | 10 | 15 |
| 5 | 4 | 9 | 2 | 3 |
Now multiply all the numbers with a black background in the table above to figure out GCF.
gcf(120, 270, 60, 40) = 30