Make delicious recipes!

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 = []

Start with 2,
P = [2]
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:

Facebook comments:

Site Owner: Sachin Goyal