# How To Find Prime Factors Of A Number (4 Key Steps)

Finding the prime factors of a number helps us to find the least common denominator (LCD), which is useful for adding fractions.  Factoring a number into large prime factors is difficult, and this difficulty is used as the basis of RSA cryptography.

So, how do you find the prime factors of a number?  First, factor out 2 until the result is no longer even. Next, factor out 3 until the sum of the digits is no longer divisible by 3. Then, factor out 5 until the last digit is no longer 5. Finally, take the square root of the result and test the primes from 7 up to that number.

Of course, some numbers will not have small prime factors (such as 2, 3, and 5).  In those cases, you can skip directly to step 4 and start dividing by 7 and larger primes to see if you get a zero remainder.

In this article, we’ll talk about how to find the prime factors of a number.  We’ll also look at examples to make the process clear so you can follow along easily.

Let’s get started.

## How To Find Prime Factors Of A Number

To find the prime factors of a number N, one approach is to divide N by the smallest prime number (which is 2) and see if you get a zero remainder. When factoring a number, we usually start by testing for divisibility by the smallest primes: 2, 3, and 5.

If so, then N is even, and has a factor of 2.  Take N/2 and try dividing by 2 again.

If not, then N is odd, and has no factor of 2.  Take N and try dividing by the next prime (which is 3).

You can continue in this way until you find the prime factors of N.  However, there are some shortcuts to help you speed up the process.

Here are four steps you can take to find the prime factors of a number N:

• First, factor out 2 as many times as possible.  As long as a number is even (its last digit is 0, 2, 4, 6, or 8), it has at least one power of 2 that you can factor out.
• Next, factor out 3 as many times as possible.  As long as the sum of a number’s digits is divisible by 3, then there is at least one power of 3 that you can factor out.
• Then, factor out 5 as many times as possible.  As long as the last digit is 5, then there is at least one power of 5 that you can factor out.
• Finally, take the square root of N.  Now we only need to test the prime numbers from 7 up to √N.

### Example 1: Finding The Prime Factors Of A Number

Let’s say we want to find the prime factors of 16.

Our first step is to factor out 2 as many times as possible.  Since 16 is even, we know that we can factor out a 2 to get:

• 16 = 2*8

Since 8 is even, we can factor out another 2 to get:

• 16 = 2*2*4

Since 4 is even, we can factor out another 2 to get:

• 16 = 2*2*2*2

Using exponents to simplify the expression, we get:

• 16 = 24

Since there are no other prime factors, we have the complete prime factorization of 16.

The corresponding factor tree is pictured below:

### Example 2: Finding The Prime Factors Of A Number

Let’s say we want to find the prime factors of 108.

Our first step is to factor out 2 as many times as possible.  Since 36 is even, we know that we can factor out a 2 to get:

• 108 = 2*54

Since 18 is even, we can factor out another 2 to get:

• 108 = 2*2*27

Since 27 is odd, we cannot factor out any more powers of 2.  So, we move to step 2 to check for powers of 3.

Now, 27 has digits of 2 and 7, and their sum is 2 + 7 = 9.  Since 9 is divisible by 3, we know that we can factor out a 3 to get:

• 108 = 2*2*3*9

Since 9 is divisible by 3, we can factor out another 3 to get:

• 108 = 2*2*3*3*3

Using exponents to simplify the expression, we get:

• 108 = 22*33

Since there are no other prime factors, we have the complete prime factorization of 108.

The corresponding factor tree is shown below:

### Example 3: Finding The Prime Factors Of A Number

Let’s say we want to find the prime factors of 150.

Our first step is to factor out 2 as many times as possible.  Since 150 is even, we know that we can factor out a 2 to get:

• 150 = 2*75

Since 75 is odd, we cannot factor out any more powers of 2.  So, we move to step 2 to check for powers of 3.

Now, 75 has digits of 7 and 5, and their sum is 7 + 5 = 12.  Since 12 has digits of 1 and 2, the sum is 1 + 2 = 3.  Since 3 is divisible by 3, we know that we can factor out a 3 to get:

• 150 = 2*3*25

The digits of 25 are 2 and 5, and their sum is 2 + 5 = 7.  Since 7 is not divisible by 3, we cannot factor out any more powers of 3.  So, we move to step 3 to check for powers of 5.

Since 25 has a last digit of 5, we can factor out a 5 to get:

• 150 = 2*3*5*5

Using exponents to simplify the expression, we get:

• 150 = 2*3*52

Since there are no other prime factors, we have the complete prime factorization of 150.

The corresponding factor tree is shown below:

### Example 4: Finding The Prime Factors Of A Number

Let’s say we want to find the prime factors of 81,000.

Our first step is to factor out 2 as many times as possible.  Since 81,000 is even, we know that we can factor out a 2 to get:

• 81,000 = 2*40,500

Since 40,500 is even, we can factor out another 2 to get:

• 81,000 = 2*2*20,250

Since 20,250 is even, we can factor out another 2 to get:

• 81,000 = 2*2*2*10,125

Since 10,125 is odd, we cannot factor out any more powers of 2.  So, we move to step 2 to check for powers of 3.

Now, 10,125 has digits of 1, 0, 1, 2, and 5, so their sum is 1 + 0 + 1 + 2 + 5 = 9.  Since 9 is divisible by 3, we know that we can factor out a 3 to get:

• 81,000 = 2*2*2*3*3,375

Now, 3,375 has digits of 3, 3, 7, and 5, so their sum is 3 + 3 + 7 + 5 = 18.  The digits of 18 are 1 and 8, so their sum is 1 + 8 = 9.  Since 9 is divisible by 3, we know that we can factor out a 3 to get:

• 81,000 = 2*2*2*3*3*1,125

Now, 1,125 has digits of 1, 1, 2, and 5, so their sum is 1 + 1 + 2 + 5 = 9.  Since 9 is divisible by 3, we know that we can factor out a 3 to get:

• 81,000 = 2*2*2*3*3*3*375

Now, 375 has digits of 3, 7, and 5, so their sum is 3 + 7 + 5 = 15.  The digits of 15 are 1 and 5, so their sum is 1 + 5 = 6.  Since 6 is divisible by 3, we know that we can factor out a 3 to get:

• 81,000 = 2*2*2*3*3*3*3*125

Now, 125 has digits of 1, 2, and 5, so their sum is 1 + 2 + 5 = 8.  8 is not divisible by 3, we cannot that factor out any more powers of 3.

We move to step 3 to factor out powers of 5.

Since 125 has a last digit of 5, we can factor out a 5 to get:

• 81,000 = 2*2*2*3*3*3*3*5*25

Since 25 has a last digit of 5, we can factor out a 5 to get:

• 81,000 = 2*2*2*3*3*3*3*5*5*5

Using exponents to simplify the expression, we get:

• 81,000 = 23*34*53

Since there are no other prime factors, we have the complete prime factorization of 81,000.

***Note: you can use the following shortcut whenever a number ends in 0.  A number that ends in zero is a multiple of 10, so it has a factor of 10 = 2*5.

If a number ends in K zeros, then it is a multiple of 10K = (2*5)K = 2K5K, so it has K powers of 2 and 5.

Here, 81,000 ends in K = 3 zeros, so we know that 2K = 23 and 5K = 53 are factors.  Then, we can just look at what is left: 81, which is 34.

### Example 5: Finding The Prime Factors Of A Number

Let’s say we want to find the prime factors of 210.

Our first step is to factor out 2 as many times as possible.  Since 210 is even, we know that we can factor out a 2 to get:

• 210 = 2*105

Since 105 is odd, we cannot factor out any more powers of 2.  So, we move to step 2 to check for powers of 3.

Now, 105 has digits of 1, 0, and 5, and their sum is 1 + 0 + 5 = 6.  Since 6 is divisible by 3, we know that we can factor out a 3 to get:

• 210 = 2*3*35

Now, 35 has digits of 3 and 5, and their sum is 3 + 5 = 8.  Since 8 is not divisible by 3, we know that we cannot factor out any more powers of 3.  So, we move to step 3 to check for powers of 5.

Since 35 has a last digit of 5, it is divisible by 5, so we can factor out a power of 5 to get:

• 210 = 2*3*5*7

Since 7 is prime, we have the complete prime factorization of 210.

### Example 6: Finding The Prime Factors Of A Number

Let’s say we want to find the prime factors of 4,092.

Our first step is to factor out 2 as many times as possible.  Since 4,092 is even, we know that we can factor out a 2 to get:

• 4,092 = 2*2,046

Since 2,046 is even, we know that we can factor out another power of 2 to get:

• 4,092 = 2*2*1,023

Since 1,023 is odd, we cannot factor out any more powers of 2.  So, we move to step 2 to check for powers of 3.

Now, 1,023 has digits of 1, 0, 2, and 3, and their sum is 1 + 0 + 2 + 3 = 6.  Since 6 is divisible by 3, we know that we can factor out a 3 to get:

• 4,092 = 2*2*3*341

Now, 341 has digits of 3, 4, and 1, and their sum is 3 + 4 + 1 = 8.  Since 8 is not divisible by 3, we know that we cannot factor out any more powers of 3.  So, we move to step 3 to check for powers of 5.

Since 341 does not end in 5, there are no powers of 5 to factor out.  So, we move to step 4: find the square root of 341 (which is √341 = 18.47) and check all the primes from 7 up to 18.47.

Then the prime numbers to check are: 7, 11, 13, and 17.  We will start with 7.

If we divide 341 by 7, we get 48 with a remainder of 5.  So, 7 is not a factor of 341.

If we divide 341 by 11, we get 31 with a remainder of 0.  So, 11 is a factor of 341.  This gives us:

• 4,092 = 2*2*3*11*31

Since 31 is also prime, we have the complete prime factorization of 4,092.

### Example 7: Finding The Prime Factors Of A Number

Let’s say we want to find the prime factors of 1,517.

Our first step is to factor out 2 as many times as possible.  Since 1,517 is odd, we cannot factor out any powers of 2.

So, we move to step 2 to check for powers of 3.  Now, 1,517 has digits of 1, 5, 1, and 7, and their sum is 1 + 5 + 1 + 7 = 14.

The digits of 14 are 1 and 5, so their sum is 1 + 4 = 5.  Since 5 is not divisible by 3, we know that we cannot factor out any powers of 3.

So, we move to step 3 to check for powers of 5.  Since 1,517 does not end in 5, it has no powers of 5 for us to factor out.

So, we move to step 4: find the square root of 1,517 (which is √1,517 = 38.95) and check all the primes from 7 up to 38.95.

Then the prime numbers to check are: 7, 11, 13, 17, 19, 23, 29, 31, and 37.  We will start with 7.

If we divide 1,517 by 7, we get 216 with a remainder of 5.  So, 7 is not a factor of 1,517.

If we divide 1,517 by 11, we get 137 with a remainder of 10.  So, 11 is not a factor of 1,517.

If we divide 1,517 by 13, we get 116 with a remainder of 9.  So, 13 is not a factor of 1,517.

If we divide 1,517 by 17, we get 89 with a remainder of 4.  So, 17 is not a factor of 1,517.

If we divide 1,517 by 19, we get 79 with a remainder of 16.  So, 19 is not a factor of 1,517.

If we divide 1,517 by 23, we get 65 with a remainder of 22.  So, 23 is not a factor of 1,517.

If we divide 1,517 by 29, we get 52 with a remainder of 9.  So, 29 is not a factor of 1,517.

If we divide 1,517 by 31, we get 48 with a remainder of 29.  So, 31 is not a factor of 1,517.

If we divide 1,517 by 37, we get 41 with a remainder of 0.  So, 37 is a factor of 1,517.

Since 41 is also prime, the complete prime factorization of 1,517 is 37*41.

### Example 8: Finding The Prime Factors Of A Number

Let’s say we want to find the prime factors of 2,431.

Our first step is to factor out 2 as many times as possible.  Since 2,431 is odd, we cannot factor out any powers of 2.

So, we move to step 2 to check for powers of 3.  Now, 2,431 has digits of 2, 4, 3, and 1, and their sum is 2 + 4 + 3 + 1 = 10

The digits of 10 are 1 and 0, so their sum is 1 + 0 = 1.  Since 1 is not divisible by 3, we know that we cannot factor out any powers of 3.

So, we move to step 3 to check for powers of 5.  Since 2,431 does not end in 5, it has no powers of 5 for us to factor out.

So, we move to step 4: find the square root of 2, 431 (which is √2,431 = 49.31) and check all the primes from 7 up to 49.31

Then the prime numbers to check are: 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, and 47.  We will start with 7.

If we divide 2,431 by 7, we get 347 with a remainder of 2.  So, 7 is not a factor of 2,431.

If we divide 2,431 by 11, we get 221 with a remainder of 0.  So, 11 is a factor of 2,431.

If we divide 221 by 13, we get 17 with a remainder of 0.  So, 13 is a factor of 221.

Since 17 is also prime, the complete prime factorization of 2,431 is 11*13*17.

## Conclusion

Now you know how to find the prime factors of a number with a process that makes your work a bit easier.