Thought Process

We need to think of a smart way to get the prime factorization of a number, this is an extremely useful tool that will be used for many problems.

One very quick way goes as follows: continuously remove all the factors of 2 from a number, we then have are left with a smaller number, which we will then remove the factors of 3,4,5 and so on.

The key here is that the number we are checking for does not have to be prime. Why?

Because we are removing the smallest prime factors already, it is impossible that the number will be divisible by 4 because 2 will have removed them all, similarly for 6, we have already checked 2 and 3 so there will be no factor of 6.

This algorithm is efficient because checking whether it is divisible by composite number takes only 1 operation