CalConverters

GCF Calculator (Greatest Common Factor)

Find the greatest common factor (GCF) of two or more numbers, explained three ways: prime factorization, listing divisors, and Euclid's algorithm.

Loading calculator…

What is the GCF?

The greatest common factor (GCF) of a set of integers is the largest positive integer that divides all of them with no remainder. It's also called the greatest common divisor (GCD) or highest common factor (HCF) — same value, different name depending on the textbook.

GCF(18,30,42)=6\text{GCF}(18, 30, 42) = 6

because 6 divides 18, 30, and 42 evenly, and no larger number does.

Three ways to find the GCF

1. Listing divisors

List every divisor of each number, then pick the largest one they share.

Example — GCF(8, 12, 20):

  • Divisors of 8: 1, 2, 4, 8
  • Divisors of 12: 1, 2, 3, 4, 6, 12
  • Divisors of 20: 1, 2, 4, 5, 10, 20
  • Shared divisors: 1, 2, 4 → GCF = 4

Simple to follow, but the list gets long fast for big numbers — this calculator only shows it when every input is 1,000,000 or smaller.

2. Prime factorization

Break each number into prime factors, then multiply the primes that are common to every number, using the lowest power each prime appears with.

Example — GCF(18, 27): 18=2×3×318 = 2 \times 3 \times 3, 27=3×3×327 = 3 \times 3 \times 3. The shared factors are 3×3=93 \times 3 = 9, so GCF = 9.

Example — GCF(20, 50, 120): 20=22×520 = 2^2 \times 5, 50=2×5250 = 2 \times 5^2, 120=23×3×5120 = 2^3 \times 3 \times 5. The common primes are 2 and 5, each at its lowest power: 21×51=102^1 \times 5^1 = 10, so GCF = 10.

Tip: Prime factorization is the mirror image of finding the LCM: GCF takes the lowest power of each shared prime; LCM takes the highest power of every prime that appears in any number.

3. Euclid's algorithm

For large numbers, repeated division beats factoring. Divide the larger number by the smaller to get a remainder, then repeat with (smaller, remainder) until the remainder is 0 — the last non-zero remainder is the GCF.

gcd⁡(a,b)=gcd⁡(b, a mod b),gcd⁡(a,0)=a\gcd(a, b) = \gcd(b, \, a \bmod b), \qquad \gcd(a, 0) = a

Example — GCF(270, 192):

270 = 1 × 192 + 78
192 = 2 × 78 + 36
78  = 2 × 36 + 6
36  = 6 × 6  + 0

The last non-zero remainder is 6, so GCF(270, 192) = 6.

Tip: Euclid's algorithm needs only a handful of steps even for huge numbers, because the remainder shrinks fast — it's the same algorithm every programming language's built-in gcd() uses internally.

GCF vs. LCM

GCF and LCM (least common multiple) are opposite extremes of the same prime-factor comparison: GCF keeps the smallest shared power of each prime, LCM keeps the largest. For two numbers they're related by:

GCF(a,b)×LCM(a,b)=a×b\text{GCF}(a, b) \times \text{LCM}(a, b) = a \times b

So once you know the GCF of two numbers, the LCM is just a×bGCF(a,b)\dfrac{a \times b}{\text{GCF}(a, b)} — no extra factoring needed.

Worked examples

Example 1 — GCF(12, 18)

Prime factors: 12=2×2×312 = 2 \times 2 \times 3, 18=2×3×318 = 2 \times 3 \times 3. Shared: 2×3=62 \times 3 = 6. Euclid confirms it: 18=1×12+618 = 1 \times 12 + 6, then 12=2×6+012 = 2 \times 6 + 0 → GCF = 6.

Example 2 — GCF(12, 18, 24)

Fold pairwise: GCF(12, 18) = 6, then GCF(6, 24) = 6. GCF = 6. (Euclid's algorithm only applies to two numbers at a time — with three or more inputs this calculator shows the prime-factorization and divisor methods instead.)

Example 3 — GCF(7, 13)

Both 7 and 13 are prime and different from each other, so they share no factor above 1. GCF = 1 — the numbers are coprime.

Frequently confused terms

TermMeansExample
GCF / GCD / HCFLargest shared factorGCF(12, 18) = 6
LCMSmallest shared multipleLCM(12, 18) = 36
CoprimeGCF = 17 and 13
Prime factorizationA number written as a product of primes18=2×3218 = 2 \times 3^2

Frequently asked questions

What is the GCF of two numbers?
The GCF (greatest common factor) is the largest positive integer that divides every number in the set with no remainder. GCF(12, 18) = 6 because 6 is the biggest number that divides both 12 and 18 evenly.
What does it mean if the GCF is 1?
A GCF of 1 means the numbers are coprime (relatively prime) — they share no common factor larger than 1. GCF(7, 13) = 1 even though neither number is small, because 7 and 13 are both prime and different from each other.
What is the difference between GCF and LCM?
GCF is the largest number that divides every input; LCM (least common multiple) is the smallest number every input divides into. They're linked by GCF(a, b) × LCM(a, b) = a × b for two numbers.
Can I find the GCF of more than two numbers?
Yes. Extend any of the three methods, or fold pairs with the identity GCF(x, y, z) = GCF(GCF(x, y), z). This calculator accepts 2 to 10 numbers at once.
Which method should I use for large numbers?
Euclid's algorithm. Listing divisors or factoring primes gets slow once numbers reach six or seven digits, but Euclid's algorithm finds the GCF of two large numbers in a handful of division steps regardless of size.
Is GCF the same thing as GCD or HCF?
Yes — Greatest Common Factor (GCF), Greatest Common Divisor (GCD), and Highest Common Factor (HCF) are three names for the exact same value. US textbooks tend to say GCF; many other regions say GCD or HCF.
Is the GCF of 0 and a number defined?
GCF(k, 0) = k for any positive k, since every number divides 0. GCF(0, 0) is undefined. This calculator requires positive integers, so it doesn't need to special-case zero.

Related calculators