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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <cmath> | |
| using namespace std; | |
| void printPrimeFactors(int n) | |
| { | |
| cout << n << " = "; | |
| for( int i = 2; i < sqrt(n); i++ ) | |
| { | |
| if( n % i == 0 ) | |
| { | |
| int exp = 0; | |
| while ( n % i == 0 ) | |
| { | |
| n = n/i; | |
| exp++; | |
| } | |
| cout << i << "^" << exp << "*"; | |
| } | |
| } | |
| if( n != 1) | |
| cout << n; | |
| cout << endl; | |
| } | |
| int main() | |
| { | |
| printPrimeFactors(36); | |
| printPrimeFactors(40); | |
| printPrimeFactors(19); | |
| printPrimeFactors(24); | |
| printPrimeFactors(96); | |
| printPrimeFactors(87); | |
| return 0; | |
| } |
by