# Finding the prime factors

##### Posted in Programming, Computer Science, Math

## Problem

While completing the Hired In Tech math section, I came across a problem set that asks you to find the prime factorization of a number.

**EXAMPLE**

- Prime factorization of 20 is 2 * 2 * 5
- Prime factorization of 1105 is 5 * 13 * 17

The idea here is to obtain a list of factors of a number, that are prime, and that multiply to that number. After hashing out my own, brutish solution, I decided to look at their solution.

It was quite interesting and hard to reason about at first. Here it is.

## Solution

To obtain the prime factorization of a number N

- Create an array/list to hold all the prime factors
*(lets call this list***primes**) - Iterate from 2 to the square root of N
*(lets all this number***i**)( 2 <= i <= Math.floor(sqrt(N)) ) - For each value of i, if N is divisible by i
- Add i to primes
- Divide N by i and replace N with the result of the division
- While N is still divisible by i repeat the above 2 steps
- At the end of iteration, N will either be 1 or greater than 1
- If N is 1 then you have obtained all the primes
- If N is greater 1, then N is the last prime number and should be added to primes.

Why does this work?

*2 is prime, but multiples of 2 are not prime (because they are multiples)*

*3 is prime, but multiples of 3 are not prime*

Let’s start at 2. By continually dividing N by 2 we eliminate/exhaust every multiple of 2 from N.

And then on to 3, Continually divide N by 3 and we eliminate/exhaust every multiple of 3 from N.

Eventually N and i (the current iterator value) will no longer be divisible. And you are done.