To get the best deal on Tutoring, call 1-855-666-7440 (Toll Free)
Top

GCF by Prime Factorization Method

Greatest Common Factor of two or more integers or numbers is the largest number that divides into each of the numbers without a remainder. Greatest Common Factor (GCF) is otherwise called Greatest Common Divisor (GCD) or Highest Common Factor (HCF).

There are three methods to calculate the greatest common factor.

  • Common Factors Method
  • Prime Factors Method
  • Successive Division Method

Related Calculators
Calculate Greatest Common Factor Calculate Prime Factors
Find Prime Factorization Calculator Prime Factorization Tree Calculator
 

Prime Factorization Method Steps

Back to Top

Prime Factors Method of computing Greatest Common Factor too involves three steps. They are:

Step 1: Compute Prime Factorization of the numbers given and list them .

Step 2: List the common factors of the numbers.

Step 3: Multiply these common prime factors. The product is the Greatest common Factor.

Examples on Prime Factorization Method

Back to Top

Given below are some of the example to find GCF by Prime Factorization Method.

Solved Examples

Question 1: Let us use the same numbers 36, 108, 240 and find the Greatest Common Factor.
Solution:
 

Step 1: Prime factorization of the numbers

36 = $\times$ 2 $\times$ 3 $\times$ 3

108 = 2 $\times$ 2 $\times$ 3 $\times$ 3 $\times$ 3

240 = $\times$ 2 $\times$ 2 $\times$ 2 $\times$ 3 $\times$ 5

Step 2: List the common prime factors of the numbers

The common factors are 2, 2, 3

Step 3: Multiply the common factors

2 $\times$ 2 $\times$ 3 = 12

Greatest Common Divisor of 36, 108, 240 is 12


 

Question 2: Find the G.C.D of 24 and 36 and 60 using prime factor method.
Solution:
 

First let us find the prime factors of the given numbers.

24 =2 $\times$ 12, 36 =2 $\times$ 18, 60 = 2 $\times$ 30

24 =2 $\times$ 2 $\times$ 6, 36 = 2 $\times$ 2 $\times$ 9, 60 = 2 $\times$ 2 $\times$ 15

24 = 2 $\times$ 2 $\times$ 2 $\times$ 3, 36 = 2 $\times$ 2 $\times$ 3 $\times$ 3, 60 = 2 $\times$ 2 $\times$ 3 $\times$ 5

The factors common to 24, 36 and 60 are 2, 2, 3

Therefore, the G.C.D of 24, 36 and 60 = 2 $\times$ 2 $\times$ 3 = 12.


 


GCF by Division Method

Back to Top

GCF of two numbers can be found out by various methods. Euclid’s algorithm is the simplest way. Euclid’s algorithm finds the GCD of two numbers by dividing the larger number by the smaller number.

Steps to Find GCF using Euclid’s Algorithm

Given below are the steps to be followed to find the GCF of two numbers with the help of Division Method.

  • First identify the larger number and the smaller number.
  • Large number / Small number
  • If there is no remainder, then the smaller number is the GCF. For example, GCF of 12 and 60 is 12. $\frac{60}{12}$ = 5 and remainder = 0
  • If we get a remainder, the divisor (small number) is divided by the remainder. Again if the remainder is 0, then the divisor is the GCF of the given numbers.
  • The same process is repeated till we get zero as the remainder.
  • If the remainder at any step is 1. Then, the numbers are relatively prime.

Example : Find the GCF of x and y.

If remainder of $\frac{x}{y}$ is 0, then, y is the GCF

$\frac{x}{y}$ gives remainder r

$\frac{y}{r}$ gives remainder a

$\frac{r}{a}$ gives remainder b

$\frac{a}{b}$ gives zero remainder .

Then, b is the GCF of x and y.

Practice Problems

Back to Top
Problem 1: Find the GCF of 245 and 65 using division method.

Problem 2: Find the GCF of 2456 and 7655 using prime factorization method.
Related Topics
Math Help Online Online Math Tutor
*AP and SAT are registered trademarks of the College Board.