Pages

Category

# GCF Calculator (Greatest Common Factor) HCF,GCD

Enter the values and select the method, the calculator will calculate the Greatest Common Factor.

GCF calculator helps to find the greatest common factors of two or more given set of numbers by using different GCF methods. Even this Greatest Common Factor Calculator can help to find the step-by-step calculation of the Greatest common divisor (GCD), Highest common factor (HCF), and Highest common divisor (HCD) for the given integers.

## What is the Greatest Common Factor(GCF)?

"The Greatest Common Factor (GCF) is the largest positive integer that divides two or more numbers without leaving a remainder"

There are different other names for the GCF of given values included:

• Highest Common Factor (HCF)
• Highest Common Divisor (HCD)

## How To Find The Greatest Common Factor With Different Methods?

The GCF finder uses the following formulas to find the greatest or highest common factors of the given data set.

### GCF By Listing Factors:

"The method of finding the Greatest Common Factor by identifying and listing all the factors of the given numbers, and then determining the largest factor that is common to all the numbers"

Here we have an example to clear the concept of calculation by listing the factors.

For Example:

What is the greatest common factors of 6,10 and 12?

Solution:

• The Factors of 6 = 1,2,3,6
• The Factors of 10 = 1,2,5,10
• The Factors of 12 = 1,2,3,4,6,12

List of all the common factors in each of integer = 1,2

Here, the greatest number which is on the list is 2.

GCF result of 6,10,12 = 2

### GCF By The Prime Factorization:

"Prime factorization is a method of finding the Greatest Common Factor by expressing each number as a product of its prime factors and then identifying the prime factors along with their lowest exponents"

For Example:

What is the Greatest Common Divisor (GCD) of 15,40 and 90?

Solution:

• Prime factorization of 15 = 1,3,5,15
• Prime factorization of 40 = 1,2,4,5,8,10,20,40
• Prime factorization of 90 = 1,2,3,5,6,9,10,15,18,30,45,90

Prime factorization = 1, 5 HCF = 1 × 5

So, the result of (Greatest Common Factor) GCF of the numbers 15, 40, 90 = 5

### GCF By Euclidean Algorithm:

"The Euclidean Algorithm is a method in which two numbers are repeatedly applying the formula GCF of (a, b) = GCF(b, a mod b) until the remainder becomes zero, at which point the non-zero divisor is the Greatest Common Factor"
• Subtract the smaller number from the larger number
• Then subtract the smaller number from the result.
• Consider the small number as a large number, subtract the result of the previous step from the new large number.
• Repeat the process, until you reach zero.
• When the result is zero, the gcf of the numbers is the number you found before the zero result.

For Example:

What is a greatest common factors of 22 and 33?

Solution:

• 33-22 = 11
• 22-11 = 11
• 11-11 = 0

So, the result of GCF (Greatest Common Factor) for the number 22 and 33 = 11.

### GCF By Binary Stein’s Algorithm:

"Binary Stein's Algorithm uses binary arithmetic operations to efficiently compute the GCF through a series of steps involving bitwise operations and conditional shifts. You simply use the comparison, subtraction and divide by 2"
• Sort all the numbers/integers in ascending order.
• Suppose the initial GCF is 1.
• Divide all the even numbers with 2.
• Subtract the first number from the remaining numbers and divide by 2.
• Repeat these steps until you obtain a single value.

For Example:

Find the gcf of 45,15 and 115?

Ascending order = 15,45,115

Solution:

Step 1:

Initial GCF is 1

Step 2:

• (45 - 15) / 2 = 15
• (115 - 15) / 2 = 50

So,

15, 50

Step 3:

Now again, divide the even value with 2 So, 15, 25

Step 4:

Subtract 25 from 15 and divided by 2.

(25-15)/2 = 5

So,

15,5

Step 5:

Now, again divide the even value with 2 and remove any duplicate value. Subtract 5 from 15 and divided by 2.

(15-5)/2 = 5

So,

5,5

Step 6:

As there is only one term left, multiply it with your initial gcf:

5*1 = 5

Therefore 5 is the greatest or highest common factors of 15,45 and 115.