Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Finding all the prime factors of a given number

Problem: Given some integer N, find all the prime factors of that number.

Solution: This is very similar to finding first N prime numbers.

1. Check with 2, then keep on checking odd numbers till 1 + (int)Math.sqrt(N)
2. For 2 and every odd number 'P':
1. If N%P != 0, ignore that number P as it cannot be a prime factor of N.
2. If N%P==0, keep on dividing N by P until it becomes indivisible by P.

Example:
```N = 132
P = []

P = 
N = 33 (repeatedly divide by 2 unless the remaining number becomes indivisible)

Next prime is 3,
P = [2,3]
N = 11

Try all odd numbers from now on, (no need to check if the odd is prime or not)
5: rejected since it does not divide 11
7: rejected since it does not divide 11
9: rejected since it does not divide 11
11: accepted, N = 1

Hence prime factors of 132 = [2, 3, 11]
```

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: