Beginning Java Data Structures and Algorithms

Prime Factorization

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