Thiago P.

Finding the prime factors

Posted in Programming, Computer Science, Math

← back to the blog


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

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

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