Enter two to five whole numbers and instantly see their greatest common factor, each number's prime factorization, and the full Euclidean algorithm working, with no submit button and no waiting.
Enter whole numbers only. Decimals are truncated and zero is ignored.
Prime factorization and Euclidean algorithm steps will appear here once two or more numbers are entered above.
The greatest common factor is the biggest building block a group of numbers shares. It is the foundation every fraction, ratio, and factoring problem eventually rests on.
The greatest common factor (GCF) of a set of numbers is the largest positive integer that divides every number in the set without leaving a remainder. For example, the GCF of 8 and 12 is 4, because 4 is the biggest number that divides both 8 and 12 evenly. No larger number works for both.
You will often see the same value called the greatest common divisor (GCD). GCF and GCD describe exactly the same calculation; GCF is the phrase most US textbooks use, while GCD shows up more in advanced math and computer science, including this calculator's underlying algorithm.
Finding the GCF is the key step in simplifying fractions to lowest terms, reducing ratios, and factoring algebraic expressions. As shown below, it also computes the least common denominator of two or more fractions without brute-force guessing.
There are three standard ways to find a greatest common factor. Small numbers are easiest to handle by listing factors; larger or multiple numbers are usually faster with prime factorization or the Euclidean algorithm.
| Method | Best for | How it works |
|---|---|---|
| Listing Factors | Best for small numbers you can factor by hand | List every factor of each number, then pick the largest value the lists share. |
| Prime Factorization | Best for numbers with several factors or larger values | Break each number into primes, then multiply the shared primes at their lowest shared power. |
| Euclidean Algorithm | Best for large numbers or fast, error-free calculation | Divide the larger number by the smaller, keep the remainder, and repeat until the remainder is zero. |
List every factor of each number, then find the largest value the lists have in common. This method is quick and visual for numbers small enough to factor in your head.
Example: GCF of 12 and 18
Break every number into its prime factors, then multiply only the primes that appear in all the numbers, each raised to the lowest power it reaches across the whole set. This scales far better than listing factors once numbers get large.
Example: GCF of 24 and 36
The Euclidean algorithm finds the GCF without factoring at all: divide the larger number by the smaller, note the remainder, then repeat the division using the smaller number and the remainder in place of the original pair. When the remainder finally hits zero, the last non-zero remainder is the GCF. It is the method computers use because it is fast even for very large numbers.
Example: GCF of 48 and 18
The greatest common factor and the least common denominator are two sides of the same coin: one divides numbers down to their shared core, the other multiplies them up to a shared total.
Because every LCM (and therefore every least common denominator) can be built directly from a GCF, you never have to search for a common denominator blindly. For denominators 24 and 30: GCF(24, 30) = 6, so the LCD is (24 × 30) ÷ 6 = 720 ÷ 6 = 120. That single division replaces a whole list of trial multiples.
Reading the ladder from the middle down, 24 and 30 both reduce to the shared factor 6, which is the GCF. Reading from the middle up, 24 and 30 both scale up to the shared multiple 120, which is the LCM and the value you would use as an LCD when adding fractions with denominators 24 and 30.
Six fully solved examples covering listing factors, prime factorization, and a three-number GCF. These show the same working style the calculator above produces automatically.
A quick lookup of common number pairs and their greatest common factor. Handy for checking homework or spotting the pattern behind the Euclidean algorithm above.
| Number A | Number B | GCF |
|---|---|---|
| 8 | 12 | 4 |
| 6 | 9 | 3 |
| 12 | 18 | 6 |
| 24 | 36 | 12 |
| 15 | 25 | 5 |
| 10 | 15 | 5 |
| 9 | 15 | 3 |
| 14 | 21 | 7 |
| 16 | 24 | 8 |
| 18 | 27 | 9 |
| Number A | Number B | GCF |
|---|---|---|
| 20 | 30 | 10 |
| 21 | 28 | 7 |
| 22 | 33 | 11 |
| 25 | 35 | 5 |
| 27 | 36 | 9 |
| 28 | 42 | 14 |
| 30 | 45 | 15 |
| 32 | 48 | 16 |
| 35 | 49 | 7 |
| 36 | 54 | 18 |