Greatest Common Factor Calculator (GCF or GCD or HCF)

What is the Greatest Common Factor?

The greatest common factor (GCF) is also referred to as the greatest common denominator (GCD) or highest common factor (HCF) but is most formally referred to as the Greatest Common Divisor (GCD). ^[1,2]

Enter the numbers you want evaluated separated by commas.

How to Find the Greatest Common Factor (GCF)

The greatest common factor of two or more whole numbers is the largest whole number that divides evenly into each of the numbers.

There are several ways to find the greatest common factor of numbers and the most efficient method you use depends on how many numbers you have, how large they are and what you will do with the result.

Factoring

To find the GCF by factoring, we list out all of the factors of each number or get them with a factor calculator.  The whole number factors are numbers that divide evenly into the number to be factored. We then list the common factors of each and choose the largest one.

Example: Find the GCF of 18 and 27

The factors of 18 are 1, 2, 3, 6, 9, 18.

The factors of 27 are 1, 3, 9, 27.

The common factors of 18 and 27 are 1, 3 and 9.

The greatest common factor of 18 and 27 is 9.

Example: Find the GCF of 20, 50 and 120

The factors of 20 are 1, 2, 4, 5, 10, 20.

The factors of 50 are 1, 2, 5, 10, 25, 50.

The factors of 120 are 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120

The common factors of 20, 50 and 120 are 1, 2, 5 and 10. (just the numbers common to all three)

The greatest common factor of 20, 50 and 120 is 10.

Prime Factorization

To find the GCF by prime factorization, we list out all of the prime factors of each number or get them with a prime factor calculator.  We then list the common prime factors for each occurrence of each and multiply these together to get the GCF .

You will see that as our numbers to factor get larger, this prime factorization method may be easier than straight factoring.

Example: Find the GCF (18,27)

The prime factorization of 18 is 2 x 3 x 3 = 18.

The prime factorization of 27 is 3 x 3 x 3 = 27.

The occurrences of common prime factors of 18 and 27 are 3 and 3.

So, the greatest common factor of 18 and 27 is 3 x 3 = 9.

Example: Find the GCF (20,50,120)

The prime factorization of 20 is 2 x 2 x 5 = 20.

The prime factorization of 50 is 2 x 5 x 5 = 50.

The prime factorization of 120 is 2 x 2 x 2 x 3 x 5 = 120.

The occurrences of common prime factors of 20, 50 and 120 are 2 and 5.

So, the greatest common factor of 20, 50 and 120 is 2 x 5 = 10.

Euclid's Algorithm

What do you do if you want to find the GCF of more than 2 very large numbers such as 182664, 154875 and 137688? If you have a calculator for factoring or a calculator for prime factorization or even this GCF calculator it would be easy but if you needed to solve the problem by hand it could become arduous.

Euclid's algorithm gives us a process for finding the GCF of 2 numbers. From the larger number, subtract the smaller number as many times as you can until you have a number that is smaller than the small number. (or without getting a negative answer) Now, using the original small number and the result, a smaller number, repeat the process. Repeat this until the last result is zero, and the GCF is the next-to-last small number result. Also see our Euclid's Algorithm Calculator.

Example: Find the GCF (18, 27)

27 - 18 = 9

18 - 9 - 9 = 0

So, the greatest common factor of 18 and 27 is 9, the smallest result we had before we reached 0.

Example: Find the GCF (20,50,120)

Note that the GCF (x,y,z) = GCF ( GCF (x,y),z). In other words, the GCF of 3 or more numbers can be found by finding the GCF of 2 numbers and using the result along with the next number to find the GCF and so on.

Let's get the GCF(120,50) first

120 - 50 - 50 = 120 - (50 * 2) = 20

50 - 20 - 20 = 50 - (20 * 2) = 10

20 - 10 - 10 = 20 - (10 * 2) = 0

So, the greatest common factor of 120 and 50 is 10.

Now let's find the GCF of our third value, 20, and our result, 10. GCF(20,10)

20 - 10 - 10 = 20 - (10 * 2) = 0

So, the greatest common factor of 20 and 10 is 10.

Therefore, the greatest common factor of 120, 50 and 20 is 10.

Example: Find the GCF (182664, 154875, 137688) or GCF ( GCF(182664, 154875), 137688)

First we find the GCF(182664, 154875)

182664 - (154875 * 1) = 27789

154875 - (27789 * 5) = 15930

27789 - (15930 * 1) = 11859

15930 - (11859 * 1) = 4071

11859 - (4071 * 2) = 3717

4071 - (3717 * 1) = 354

3717 - (354 * 10) = 177

354 - (177 * 2) = 0

So, the the greatest common factor of 182664 and 154875 is 177.

Now we find the GCF(177, 137688)

137688 - (177 * 777) = 159

177 - (159 * 1) = 18

159 - (18 * 8) = 15

18 - (15 * 1) = 3

15 - (3 * 5) = 0

So, the greatest common factor of 177 and 137688 is 3.

Therefore, the greatest common factor of 182664, 154875 and 137688 is 3.

Programming (php) to find the greatest common factor of 2 or more values using Euclid's Algorithm

We can create a script that uses Euclid's Algorithm to find the GCF of 2 or more numbers. Of course you will need to handle user inputs such as 0's, negative values or only 1 value if you are setting up your own calculator but this is the core script.

// set up an array of values to be evaluated
$values = array(225, 45, 15, 540)

// count the number of values in the array
$num_values = count($values);

// get the first 2 values in the array        
$x = current($values);
$y = next($values);

// set up the larger and smaller of the values and initialize the result c
$a = max( $x, $y );
$b = min( $x, $y );
$c = 1;

// set up a for-loop to check through all of the values in the array
// the first pass will check 2 numbers then each additional pass will check 1
// make ($num_values - 1) passes
for ($i = 1; $i < $num_values; $i ++)
{
    // find the GCF of $a and $b
    // it will be found when $c == 0 in the next do-while-loop
    do 
    {
        // subtract the lower number from the higher as many times as possible
        // until our result is lower than the lower number
        // this will do until $c is less than $b but not less than 0
        do
        {
            $c = $a - $b;
            $a = $c;
        } 
        while ($c  >  $b);

        // capture last value of $b as the potential last GCF result
        $gcf = $b;
        
        // if $c did not = 0 we need to repeat with the values held in $b and $c
        // at this point $b is higher than $c so we set up for the next iteration
        // set $a to the higher number and $b to the lower number
        $a = $b;
        $b = $c;
            
    }
    while ($c != 0);
    
    // if $c did == 0 then we have found the GCF of 2 numbers
    // now set up to find the GCF of the last GCF we found
    // and the next value in the array()
    $x = $gcf;
    $y = next($values);
    
    $a = max( $x, $y );
    $b = min( $x, $y );
    $c = 1;
    
}  // end for loop through array()  

//
// the greatest common factor of our array of values is now held in $gcf
//

Programming (php) to find the greatest common factor more efficiently

Using Euclid's Algorithm to construct a php script to find the GCF of 2 or more numbers works very well. However, the process in the algorithm is the same as the dividing one number by another and using the remainder.  For this we can substitute the modulus funclion (%). a mod b is the remainder of a divided by b. We also move the initialization of $a and $b to the inside of the for-loop only.

// set up an array of values to be evaluated
$values = array(225, 45, 15, 540)

// count the number of values in the array
$num_values = count($values);

// get the first 2 values in the array        
$x = current($values);
$y = next($values);
    
// set up a for-loop to check through all of the values in the array
// the first pass will check 2 numbers then each additional pass will check 1
// make ($num_values - 1) passes
for ($i = 1; $i < $num_values; $i ++)
{
    // set up the larger and smaller of the values
    $a = max( $x, $y );
    $b = min( $x, $y );
    $c = 1;

    // find the GCF of $a and $b
    // it will be found when $c == 0
    do 
    {
        $c = $a % $b;

        // capture last value of $b as the potential last GCF result
        $gcf = $b;
        
        // if $c did not = 0 we need to repeat with the values held in $b and $c
        // at this point $b is higher than $c so we set up for the next iteration
        // set $a to the higher number and $b to the lower number
        $a = $b;
        $b = $c;
            
    }
    while ($c != 0);
    
    // if $c did == 0 then we have found the GCF of 2 numbers
    // now set up to find the GCF of the last GCF we found
    // and the next value in the array()
    $x = $gcf;
    $y = next($values);
    
}  // end for loop through array()

//
// the greatest common factor of our array of values is now held in $gcf
//

              

References

[1] Zwillinger, D. (Ed.). CRC Standard Mathematical Tables and Formulae, 31st Edition New York, NY: CRC Press, 2003 p. 101.

[2] Weisstein, Eric W. "Greatest Common Divisor." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/GreatestCommonDivisor.html

http://www.helpwithfractions.com/greatest-common-factor.html

http://mathforum.org/library/drmath/view/58134.html

http://en.wikipedia.org/wiki/Euclidean_algorithm