- 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.
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.