Greatest Common Factor Calculator

Greatest Common Factor Calculator

Greatest Common Factor Calculator (GCF), also known as greatest common divisor (GCD), highest common factor (HFC) or greatest common denominator (GCD) are the exact same things but under a different name. If you want to calculate the GCF, GCD, HFC or GCD of two or more numbers, this is the perfect place to do that very easy and fast.

What is the Greatest Common Factor?

The Greatest Common Factor (GCF) calculated from two or more integers will be the greatest positive integer that will divide evenly into all the numbers that you picked in your set, without a remainder. If you’re wondering how you can find the highest common factor from a set of numbers, you should know that there are several methods to do that, but firstly you should see an example to understand exactly what the greatest common factor is.

For example, if you want to find the GFC for the following values: 6,9,18,12 the result for your set of values will be 3. As we said before, there are different methods that can be used to calculate the greatest common factor, so you can use the factoring method, Euclid’s Algorithm or the prime factorization. Let’s start with the first one.

Using the Greatest Common Factor Calculator

Number of Values :




Factoring step by step

Greatest Common Factor Calculator

Finding the greatest common factor with this method implies to find all the factors for each number from your set of values. After this first step, you’ll have to compare the common factors for each number from your set and to pick the largest one. That one will be the GFC for the your set of values. Take a look at the following example and you’ll understand exactly how this method works.

Example:

  • Your set of values is: 24, 30, 12, 36, 18.
  • The factors for 24 will be: 1, 2, 3, 4, 6, 8, 12 and 24.
  • The factors for 30 will be: 1, 2, 3, 5, 6, 10, 15 and 30.
  • The factors for 12 will be: 1, 2, 3, 4, 6 and 12.
  • The factors for 36 will be: 1, 2, 3, 4, 6, 9, 12, 18 and 36.
  • Finally, the factors for 18 will be: 1, 2, 3, 6, 9 and 18.

The common factors between 24, 30, 12, 36 and 18 are 1, 2, 3 and 6. As we said in the beginning, you’ll have to pick the highest value between these common factors, which in this case will be 6. So the Greatest Common Factor for 24, 30, 12, 36 and 18 is 6.

Euclid’s Algorithm

Euclid’s Algorithm for GCF is usually used when you have two or more very large numbers, but it can also be used for small numbers as well. The algorithm says that if you want to find the GCF between two numbers you have to subtract the smaller number from the larger one, as many times possible, until you’ll get a number smaller than the number that you considered small in the beginning of the process (without having a negative number).

The process continues by following the same algorithm, but now you will use the small number from the beginning and you will subtract from that one the result form the last step. You need to repeat this until you will get zero as the last result. In the end, you’ll find the GFC which will be the penultimate small number result.

Let’s see an example when it’s easier to use the Euclid’s Algorithm to find the GCF between 816 and 2260.

Firstly, we will subtract the smaller number, 816, from 2260 as many times as we can:

  • 2260-816=1444
  • 1444-816=628

Now we’ll subtract the smaller number that we just obtained, 628, from the bigger one, which now is 816.

  • 816-628=188

We’ll repeat the process, as we described above.

  • 628-188=440
  • 440-188=252
  • 252-188=64

Again, we obtained a smaller number, so we will switch again.

  • 188-64=124
  • 124-64=60

It’s the same thing now, 60 < 64, so we will have to subtract 60 from 64.

  • 64-60=4

We can see that now we’ll have to subtract 4 from 60, and we’ll be able to do that for 15 times and in the end we’ll get 0.

  • 60-(4×15)=0.

“0” is the ultimate (the final) result, and the penultimate result will be “4”. Greatest common factor between 816 and 2260 is 4.

GCF of three or more numbers is easy to find by getting first the GCF of two of them, and then using the result with the next numbers. GCF(a,b,c)=GCF(GCF(a,b),c).

Prime Factorization

If you want to use the Prime Factorization method to get the Greatest Common Factor, you’ll have to list all the prime factors for each number from your set of values. The next step is to pick the common prime factors of your original numbers and to include the biggest number of occurrences of each common prime factor of the original number. In the end, you’ll have to multiply these numbers to obtain the greatest common factor.

Let’s use the same set of values that we used for the factoring method: 24, 30, 12, 36, 18.

  • The prime factorization for 24 will be 2 x 2 x 2 x 3 = 24
  • The prime factorization for 30 will be 2 x 3 x 5 = 30
  • The prime factorization for 12 will be 2 x 2 x 3 = 12
  • The prime factorization for 36 will be 2 x 2 x 3 x 3 = 36
  • The prime factorization for 18 will be 2 x 3 x 3 = 18

The highest number of occurrences of each prime number for our set of values are 2 and 3, so, as the algorithm says, we have to multiply them to get the result.

In our case, the final result will be 2 x 3 = 6, and as we expected, the greatest common factor between 24, 30, 12, 36, 18 is also 6 with this method.

Leave a Comment