Greatest Common Factor Calculator

About this calculator

Enter two or more positive whole numbers separated by commas to get their greatest common factor: the largest number that divides every one of them with no remainder.

The work is shown three ways: the list of factors, prime factorization, and the Euclidean algorithm.

Positive whole numbers, up to 18 digits each.
Embed this calculator

Paste this code into a Custom HTML block on your site. The calculator fits the width of the block. Adjust the height in the code if you want more room for results.

Find this widget in the publisher directory

What is the greatest common factor?

A factor (or divisor) of a number divides it exactly. The greatest common factor of several numbers is the biggest value that is a factor of all of them. It goes by other names too: greatest common divisor (GCD), highest common factor (HCF) and greatest common measure. For 12 and 18 the common factors are 1, 2, 3 and 6, so the GCF is 6.

The GCF is the tool behind simplifying fractions. To reduce 18/24, divide the top and bottom by GCF(18, 24) = 6 and you land on 3/4 in a single step.

Method 1: list the factors

Write every factor of each number, circle the ones that appear everywhere, and pick the largest. It is easy to follow and fine for numbers under a few hundred, but the lists grow quickly.

Method 2: prime factorization

Write each number as a product of primes, keep the primes shared by all of them, and multiply those together using the smallest exponent of each. For 16, 88 and 104:

  • 16 = 2 × 2 × 2 × 2
  • 88 = 2 × 2 × 2 × 11
  • 104 = 2 × 2 × 2 × 13

Three 2s are common to all three, so the GCF is 2 × 2 × 2 = 8.

Method 3: the Euclidean algorithm

Euclid noticed that the GCF of two numbers does not change if you replace the larger by its remainder after dividing by the smaller. Repeat until the remainder is zero, and the last nonzero remainder is the answer.

GCD(a, b) = GCD(b, a mod b), stop when b = 0

Example with 268,442 and 178,296:

DivisionRemainder
268,442 = 1 × 178,296 + 90,14690,146
178,296 = 1 × 90,146 + 88,15088,150
90,146 = 1 × 88,150 + 1,9961,996
88,150 = 44 × 1,996 + 326326
1,996 = 6 × 326 + 4040
326 = 8 × 40 + 66
40 = 6 × 6 + 44
6 = 1 × 4 + 22
4 = 2 × 2 + 00

The chain finishes with a last nonzero remainder of 2, so GCD(268,442, 178,296) = 2. Because numbers this size would be painful to factor by hand, the Euclidean algorithm is the method of choice for large inputs.

More than two numbers

The GCF is associative, so for a list you compute it pairwise and carry the result forward: GCD(a, b, c) = GCD(GCD(a, b), c). Continuing the example, GCD(268,442, 178,296, 66,888) = GCD(2, 66,888) = 2.

Handy facts

  • If the GCF is 1 the numbers are called coprime or relatively prime.
  • The GCF can never exceed the smallest number in the list.
  • If one number divides all the others, it is the GCF.
  • For two numbers, GCF × LCM equals the product of the numbers.

Worked example

Find GCF(330, 75, 450, 225). The factorizations are 330 = 2 × 3 × 5 × 11, 75 = 3 × 5 × 5, 450 = 2 × 3 × 3 × 5 × 5 and 225 = 3 × 3 × 5 × 5. The only primes present in every number are one 3 and one 5, so the GCF is 3 × 5 = 15.

Choosing a method

For small numbers, listing factors is the most intuitive way to see what is going on, and it makes a good teaching aid. Prime factorization is the best choice when you also want the least common multiple, since the same factorizations feed both answers. The Euclidean algorithm wins whenever the numbers are big or you only need the GCF, because each step shrinks the problem dramatically: the remainder is always less than half of the larger number after two steps, so even 18-digit inputs finish in under a hundred divisions.

Real-world uses

  • Cutting a 48 by 36 inch board into the largest possible identical squares: the side is GCF(48, 36) = 12 inches.
  • Splitting 56 red and 42 blue marbles into identical bags with nothing left over: at most GCF(56, 42) = 14 bags.
  • Reducing ratios such as 150:90 to 5:3 by dividing both sides by 30.
  • Finding the common period of two repeating gear teeth or schedule patterns.

Frequently asked questions

Are GCF, GCD and HCF the same thing?

Yes. Greatest common factor, greatest common divisor and highest common factor all name the largest integer that divides every number in the set.

What is the GCF of two prime numbers?

It is 1, unless they are the same prime. Two different primes share no factor other than 1.

How do I use the GCF to simplify a fraction?

Divide the numerator and denominator by their GCF. For 42/56 the GCF is 14, so the fraction reduces to 3/4.

What if the GCF is 1?

Then the numbers are coprime. A fraction made from them is already in lowest terms.

Formulas and sample results on this page were checked against independent references. Page last reviewed or updated . How we verify calculators. Project led by Shaun Connell.