Greatest Common Factor Calculator
Please provide numbers separated by a comma "," and click the "Calculate" button to find the GCF.
What is the Greatest Common Factor (GCF)?
In mathematics, the greatest common factor (GCF), also known as the greatest common divisor, of two (or more) non-zero integers a and b, is the largest positive integer by which both integers can be divided. It is commonly denoted as GCF(a, b). For example, GCF(32, 256) = 32.
Prime Factorization Method
There are multiple ways to find the greatest common factor of given integers. One of these involves computing the prime factorizations of each integer, determining which factors they have in common, and multiplying these factors to find the GCF. Refer to the example below (the common factors are underlined).
16 = 2 × 2 × 2 × 2
88 = 2 × 2 × 2 × 11
104 = 2 × 2 × 2 × 13
GCF(16, 88, 104) = 2 × 2 × 2 = 8
Prime factorization is only efficient for smaller integer values. Larger values would make the prime factorization of each and the determination of the common factors far more tedious.
Euclidean Algorithm
Another method used to determine the GCF involves using the Euclidean algorithm. This method is far more efficient than prime factorization. It uses a division algorithm combined with the observation that the GCF of two integers also divides their difference. The algorithm is as follows:
GCF(a, b) = GCF(a − b, b), when a > b
GCF(a, b) = GCF(a, b − a), when b > a
In practice, repeatedly replace the larger of the two numbers by the remainder of the division until the remainder is 0; the GCF is the remainder from the step before the zero result:
268442 = 178296 × 1 + 90146
178296 = 90146 × 1 + 88150
90146 = 88150 × 1 + 1996
88150 = 1996 × 44 + 326
1996 = 326 × 6 + 40
326 = 40 × 8 + 6
40 = 6 × 6 + 4
6 = 4 × 1 + 2
4 = 2 × 2 + 0 → GCF = 2
If more integers were present, the same process would be performed to find the GCF of the subsequent integer and the GCF of the previous two integers. Referring to the previous example, if instead the desired value were GCF(268442, 178296, 66888), after having found that GCF(268442, 178296) is 2, the next step would be to calculate GCF(66888, 2). In this particular case, it is clear that the GCF would also be 2, yielding GCF(268442, 178296, 66888) = 2.
Frequently Asked Questions
What is the greatest common factor (GCF)?
The greatest common factor of two or more non-zero integers is the largest positive integer that divides all of them. It is also called the greatest common divisor (GCD) and is written GCF(a, b): for example, GCF(32, 256) = 32.
How do you find the GCF by prime factorization?
Factor each number into primes, find the factors they all share (each prime at the smallest count it appears with in any one number), and multiply those common factors together. For 16, 88, and 104 the shared factors are 2 × 2 × 2, so the GCF is 8.
What is the Euclidean algorithm?
A faster method for two numbers: replace the larger number by the remainder of dividing the larger by the smaller, and repeat until the remainder is 0. The last non-zero remainder is the GCF. For more than two numbers, apply it in stages, carrying the GCF forward.
What is the GCF if the numbers share no prime factors?
The GCF is 1 — the numbers are called coprime, or relatively prime. For example, GCF(7, 13) = 1, even though neither number is 1 itself.