Factorize Number with Vector and Pair

Submitted by DoctorSpeedCode on Friday, August 8, 2014 - 05:37.
We'll see how you can factorize a natural number, using vector and pair from the C++ STL! First, you need the following declarations:
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4.  
  5. using namespace std;
  6.  
  7. vector< pair<int, int> > factors;
  8. int n;
The pairs will contain: - first element is the DIVISOR - second element is the EXPONENT Having these settled, let's move on to reading the number and starting the factorization! We will begin by computing the exponent of 2, because after having 2 as a divisor (in case the number is even), the other divisors are in the form of (2N+1), where N>=1 and N is a natural number.
  1.     n = 0;
  2.     cout << " x = ";
  3.     cin >> x;
  4.     int x_original = x;
  5.     int div = 2;
  6.     int nrd = 0;
  7.     while (x % 2 == 0) {
  8.         nrd++;
  9.         x /= 2;
  10.     }
  11.     if (nrd > 0) {
  12.         factors.push_back(make_pair(2, nrd));
  13.     }
If we have 2 as a divisor, we add it to our vector. Then, we move on to the next divisors and calculate all exponents simply! This is done like this:
  1.     div = 3;
  2.     while (x > 1) {
  3.         nrd = 0;
  4.         while (x % div == 0) {
  5.             x /= div;
  6.             nrd++;
  7.         }
  8.         if (nrd > 0) {
  9.             factors.push_back(make_pair(div, nrd));
  10.         }
  11.         div += 2;
  12.     }
This is a pretty simple method, we try with any good divisor and always increase the divisor by 2, to ensure it is (2N+1). We also set the number of divisors back to zero on every new try - this is very important! Then, we need the output:
  1.     bool first = true;
  2.     vector< pair<int, int> >::iterator it;
  3.     cout << endl << x_original << " = ";
  4.     for (it = factors.begin(); it != factors.end(); it++) {
  5.         if (first == false) {
  6.             cout << " * ";
  7.         } else {
  8.             first = false;
  9.         }
  10.         cout << (*it).first << "^" << (*it).second;
  11.     }
To avoid confusion or ugly output, such as an extra '*' in the end, we have created a bool variable and we always output the '*' at the beginning of the for loop. If you don't add it like that, you will see a wrong output or need to use control character '\b' to remove the unwanted characters. The output is simple, as we use an iterator to loop through the vector. Due to the way we computed the factors, they are already sorted from low to high. The full main.cpp source code is here:
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4.  
  5. using namespace std;
  6.  
  7. vector< pair<int, int> > factors;
  8. int n;
  9.  
  10. int main(int argc, char** argv) {
  11.     int x;
  12.     n = 0;
  13.     cout << " x = ";
  14.     cin >> x;
  15.     int x_original = x;
  16.     int div = 2;
  17.     int nrd = 0;
  18.     while (x % 2 == 0) {
  19.         nrd++;
  20.         x /= 2;
  21.     }
  22.     if (nrd > 0) {
  23.         factors.push_back(make_pair(2, nrd));
  24.     }
  25.     div = 3;
  26.     while (x > 1) {
  27.         nrd = 0;
  28.         while (x % div == 0) {
  29.             x /= div;
  30.             nrd++;
  31.         }
  32.         if (nrd > 0) {
  33.             factors.push_back(make_pair(div, nrd));
  34.         }
  35.         div += 2;
  36.     }
  37.  
  38.     bool first = true;
  39.     vector< pair<int, int> >::iterator it;
  40.     cout << endl << x_original << " = ";
  41.     for (it = factors.begin(); it != factors.end(); it++) {
  42.         if (first == false) {
  43.             cout << " * ";
  44.         } else {
  45.             first = false;
  46.         }
  47.         cout << (*it).first << "^" << (*it).second;
  48.     }
  49.     cout << endl;
  50.     return 0;
  51. }
The output will be something like this: x = 120 120 = 2^3 * 3^1 * 5^1 Enjoy!
Tags
cpp