Prime factorization is determining the prime factors of a given number. It is very difficult to build a general-purpose algorithm for this computationally hard problem. A general purpose algorithm that is commonly used to factorize primes was introduced in Chapter 1, Algorithms and Complexities. Its basic idea is to iterate through possible factors attempting to divide the number.

Start with 2; while the number is divisible by 2, keep dividing it, and add 2 to the list of factors. Afterwards, the number must be odd, so start a loop that checks for possible factors from 3 to the square root of the number.

Since we've already covered even numbers, you can do increments of 2 in this loop (there's no need to check 4, 6, 8, and so on once you've already checked 2). Once you find a suitable divisor, add the number to the list of factors and divide it until it is possible. At the end of this step, if we are left with a number greater than 2, then it is a prime number and therefore a prime factor of itself.