How do we write a program to find the prime factorization of a given number?
For example prime factorization for 18 can written as 2 * 3 * 3 or 2 * 3 ^ 2.
For any number there is only one possible prime factorization.
An efficient algorithm can be given as follows. we run a loop with i ranging from 2 to sqrt(n). In each iteration, we try to reduce the number by dividing it with i as many times as possible. As we examined in the last post, we can find all the factors of a number by checking the divisibility of it from 1 to square root of n itself.
Here is the C++ code to do this.