GCF Calculator (Greatest Common Factor)
MathChoose how many numbers you have and enter them. The calculator finds their greatest common factor and shows both ways to get it: the prime factorization and the successive divisions of the Euclidean algorithm.
Step by step
GCF(12, 18) = 6
- Write 12 and 18 as products of primes, as shown in the prime factorization table.
- Multiply the primes they share, each with its smallest exponent: 2 · 3 (if they share none, the product is 1).
- The product is the greatest common factor: 6.
- The successive divisions of the Euclidean algorithm give the same result: the last divisor, the one that leaves remainder 0, is 6.
Once every entry is valid, you’ll see each step of the calculation here.
Formula
- GCF
- the greatest common factor, the largest whole number that divides all the numbers
- pi
- the primes that divide every one of the numbers
- mi
- the smallest exponent with which that prime appears in the factorizations
- q, r
- the quotient and the remainder when a is divided by b, with r smaller than b
How it works
Any set of positive whole numbers has a greatest common factor (GCF): the largest whole number that divides each of them evenly. The same idea is called the greatest common divisor (GCD) in higher math and programming and the highest common factor (HCF) in the UK. The factors of 12 are 1, 2, 3, 4, 6 and 12, and the factors of 18 are 1, 2, 3, 6, 9 and 18. The common factors are 1, 2, 3 and 6, and the largest is 6, so the GCF of 12 and 18 is 6. When the GCF is 1, the numbers are called relatively prime or coprime.
The first method is prime factorization. Write every number as a product of primes, keep the primes that appear in all of the numbers, and multiply them, each with its smallest exponent. This is the method most students learn in school, and the calculator shows the factorization of each number in the table under the result. The second method is the Euclidean algorithm. It needs no factoring: divide the larger number by the smaller one, then divide the divisor by the remainder, and repeat until the remainder is 0. The last divisor is the GCF. It is the faster way for large numbers. With three or four numbers, the calculator finds the GCF of the first two and then the GCF of that result and the next number. The second table lists every division.
The GCF has many everyday uses. It reduces a fraction to lowest terms by dividing the top and the bottom by their GCF, so 36/60 becomes 3/5 after dividing by 12. It simplifies a ratio in the same way and splits things into equal groups with nothing left over: 48 pencils and 72 erasers make at most 24 identical kits. In the Common Core standards, finding the GCF of two whole numbers up to 100 is a grade 6 skill. To simplify a fraction step by step, use the fraction calculator; for ratios, use the ratio calculator.
The formula
With prime factorization, 12 = 2² · 3 and 18 = 2 · 3². The primes 2 and 3 appear in both, and the smallest exponent of each is 1, so the GCF is 2 · 3 = 6. A prime that is missing from one number does not enter the product. If no prime is shared, the GCF is 1.
The Euclidean algorithm works because GCF(a, b) = GCF(b, r), where r is the remainder of a divided by b. Each division swaps the pair for a smaller pair with the same GCF, so a remainder of 0 comes quickly. For 18 and 12: 18 = 1 · 12 + 6, then 12 = 2 · 6 + 0, and the last divisor is 6. For two numbers, GCF times LCM equals the product of the numbers: 6 · 36 = 12 · 18.
Example
A teacher has 48 pencils and 72 erasers and wants identical kits with nothing left over. How many kits is the most she can make?
- The most kits is the greatest common factor of 48 and 72. Prime factorization: 48 = 2⁴ · 3 and 72 = 2³ · 3².
- The shared primes with their smallest exponents are 2³ and 3: 2³ · 3 = 24.
- With divisions: 72 = 1 · 48 + 24 and 48 = 2 · 24 + 0, so the last divisor is 24. That makes 24 kits, each with 2 pencils and 3 erasers.
The GCF of 48 and 72 is 24. It is the largest whole number that divides both without a remainder.
Load this example into the calculatorFrequently asked questions
What is the greatest common factor?
The greatest common factor of a set of whole numbers is the largest whole number that divides every one of them with no remainder. For 30 and 45 it is 15, because 15 divides both and no larger number does. It exists and is unique for positive whole numbers, which is all this calculator accepts. A set made only of zeros has none, because every whole number divides 0.
How does a GCF calculator work?
It uses the same two methods you can use by hand. It factors each number into primes and multiplies the shared primes with their smallest exponents, and it also runs the Euclidean algorithm of repeated division. Both give the same answer, and both are shown under the result.
What is the greatest common factor of 52 and 104?
It is 52. The smaller number divides the larger one exactly, since 104 = 2 · 52, so the GCF is the smaller number. In primes, 52 = 2² · 13 and 104 = 2³ · 13, and the shared part is 2² · 13 = 52.
What are the common factors of 24 and 36?
The common factors of 24 and 36 are 1, 2, 3, 4, 6 and 12. The factors of 24 are 1, 2, 3, 4, 6, 8, 12 and 24, and the factors of 36 are 1, 2, 3, 4, 6, 9, 12, 18 and 36. The largest one they share, 12, is the GCF.
What is the highest common factor of 12 and 18?
It is 6. "Highest common factor" (HCF) is the name used in the UK and India for the same number that US textbooks call the greatest common factor (GCF) and that math and computing call the greatest common divisor (GCD). All three names mean the same thing.
What is a GCD function?
A GCD function returns the greatest common divisor of the numbers you give it, which is the same as the GCF. Spreadsheets have one, for example =GCD(48, 72) in Excel and Google Sheets returns 24, and programming languages such as Python offer math.gcd. This calculator does the same job and also shows the steps.
Why is the GCF important?
It lets you break a quantity into the largest equal parts. You use it to reduce fractions and simplify ratios, to share items into identical groups with none left over, and to cut a space into the largest square pieces. It is also the starting point for finding the least common multiple.
Why is the GCF important in fractions?
Dividing the numerator and the denominator by their GCF reduces a fraction to lowest terms in a single step. The GCF of 36 and 60 is 12, so 36/60 becomes 3/5. Using a smaller common factor still works but takes several rounds.
What is the difference between GCF and LCM?
The GCF is the largest number that divides all the numbers, so it is never larger than the smallest one. The least common multiple (LCM) is the smallest number that all of them divide, so it is never smaller than the largest one. For 12 and 18 the GCF is 6 and the LCM is 36, and 6 · 36 = 12 · 18.
Can a GCF calculator solve problems with more than two numbers?
Yes. This one takes two, three or four numbers. For more than two it uses GCF(a, b, c) = GCF(GCF(a, b), c), so it finds the GCF of two numbers at a time. For 48, 180 and 300 the GCF of 48 and 180 is 12, and the GCF of 12 and 300 is also 12.
When are two numbers relatively prime?
They are relatively prime (coprime) when their GCF is 1. The numbers do not have to be prime themselves: 8 and 15 are relatively prime because 8 = 2³ and 15 = 3 · 5 share no prime. The calculator points this out when the GCF is 1.
What is the GCF of equal numbers, or when one number divides the other?
The GCF is the smaller number. GCF(7, 7) = 7, and GCF(3, 6) = 3 because 3 already divides 6. The calculator accepts whole numbers from 1 up to one trillion (1,000,000,000,000).
- Common Core State Standards for Mathematics, Grade 6, The Number System, 6.NS.B.4: greatest common factor and least common multiple (Common Core State Standards Initiative)
- Elements, Book VII, Proposition 2: finding the greatest common measure of two numbers (the Euclidean algorithm) (Euclid, edited by D. E. Joyce, Clark University)
- Greatest common divisor (Wikipedia)
- Euclidean algorithm (Wikipedia)