Greatest Common Factor Calculator
Find the greatest common factor (GCF, also called GCD or HCF) of two or more numbers, with the common factors, each number's factors and prime factors, and the Euclidean algorithm step by step.
Change the values and press Calculate to work out your own figures.
GCF of two or more numbers
Enter two or more numbers to find their greatest common factor, their common factors and each number's factors and prime factors.
| Number | Prime factors | Factors |
|---|---|---|
| 330 | 2 × 3 × 5 × 11 | 1, 2, 3, 5, 6, 10, 11, 15, 22, 30, 33, 55, 66, 110, 165, 330 |
| 75 | 3 × 5 × 5 | 1, 3, 5, 15, 25, 75 |
| 450 | 2 × 3 × 3 × 5 × 5 | 1, 2, 3, 5, 6, 9, 10, 15, 18, 25, 30, 45, 50, 75, 90, 150, 225, 450 |
| 225 | 3 × 3 × 5 × 5 | 1, 3, 5, 9, 15, 25, 45, 75, 225 |
Show the working
- 330 = 2 × 3 × 5 × 11
- 75 = 3 × 5 × 5
- 450 = 2 × 3 × 3 × 5 × 5
- 225 = 3 × 3 × 5 × 5
- Prime factors they all share: 3 × 5 → GCF = 15
Euclidean algorithm (two numbers)
Find the GCF of two numbers by repeated division, with every step of Euclid's algorithm.
| Dividend | Divisor | Quotient | Remainder |
|---|---|---|---|
| 135 | 95 | 1 | 40 |
| 95 | 40 | 2 | 15 |
| 40 | 15 | 2 | 10 |
| 15 | 10 | 1 | 5 |
| 10 | 5 | 2 | 0 |
Show the working
- 135 = 95 × 1 + 40
- 95 = 40 × 2 + 15
- 40 = 15 × 2 + 10
- 15 = 10 × 1 + 5
- 10 = 5 × 2 + 0
- The remainder is 0, so the last divisor, 5, is the GCF.
How to use it
Enter two or more numbers to find their greatest common factor, their common factors and each number's factors and prime factors. Find the GCF of two numbers by repeated division, with every step of Euclid's algorithm.
The answer is exact: whole numbers of any size up to 30 digits are handled without rounding, and Show the working lists every step.
Key facts
GCF(a, b) = GCF(b, a mod b); GCF(a, 0) = a GCF × LCM = a × b (for two numbers)
Three ways to find the GCF
List the factors of each number and take the largest one they share; this is what the table shows. Or break each number into primes and multiply the primes they all share; the working shows this. Or use Euclid's algorithm: divide the larger number by the smaller, then divide the divisor by the remainder, and repeat until the remainder is 0. The last divisor is the GCF. Euclid's method is by far the fastest for large numbers.
GCF, GCD and HCF
The greatest common factor, greatest common divisor and highest common factor are the same number. It is used to simplify fractions: dividing the top and bottom of 18/24 by their GCF, 6, gives 3/4.
Questions
What is the GCF of 12 and 18?
6: the factors of 12 are 1, 2, 3, 4, 6, 12 and of 18 are 1, 2, 3, 6, 9, 18, and the largest they share is 6.
What is the GCF of 0 and a number?
The number itself, because every number divides 0.
Formulas
GCF(a, b) = GCF(b, a mod b); GCF(a, 0) = a GCF × LCM = a × b (for two numbers)
Sources
Limitations
- Numbers have at most 30 digits; factor lists and prime factorizations are limited to 10¹².