Print prime factorization in exponential form in C++

Question

So far I have this code. I'm trying to print prime factorization with exponents. For example, if my input is 20, the output should be 2^2, 5

#include <iostream>
#include <cmath>
using namespace std;

void get_divisors (int n);
bool prime( int n);
int main(int argc, char** argv) {
   int n = 0 ;
cout << "Enter a number and press Enter: ";
cin >>n;
cout << " Number n is " << n << endl;
get_divisors(n);
cout << endl;

return 0;
}
void get_divisors(int n){
  double sqrt_of_n = sqrt(n);
  for (int i =2; i <= sqrt_of_n; ++i){
    if (prime (i)){


      if (n % i == 0){
        cout << i << ", "; 
        get_divisors(n / i);
        return;
      }
    }
  }
  cout << n;
}
bool prime (int n){
double sqrt_of_n = sqrt (n);
for (int i = 2; i <= sqrt_of_n; ++i){
  if ( n % i == 0) return 0;
  }
return 1;
}

I hope someone can help me with this.

Please indicate the sample input, the expected output, and the observed output. Also, see [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). — R Sahu, Oct 30 '19 at 22:26
Unrelated: Rather than computing primes every time and repeating a lot of work for each prime number checked, [memoize the results](https://en.wikipedia.org/wiki/Memoization). You may find prime number sieving algorithms help with this and are much MUCH faster than the brute force approach. — user4581301, Oct 30 '19 at 22:51

score 2 · Accepted Answer · answered Oct 30 '19 at 23:06

You can use an std::unordered_map<int, int> to store two numbers (x and n for x^n). Basically, factorize the number normally by looping through prime numbers smaller than the number itself, dividing the number by the each prime as many times as possible, and recording each prime you divide by. Each time you divide by a prime number p, increment the counter at map[p].

I've put together a sample implementation, from some old code I had. It asks for a number and factorizes it, displaying everything in x^n.

#include <iostream>
#include <unordered_map>
#include <cmath>


bool isPrime(const int& x) {
    if (x < 3 || x % 2 == 0) {
        return x == 2;
    } else {
        for (int i = 3; i < (int) (std::pow(x, 0.5) + 2); i += 2) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}

std::unordered_map<int, int> prime_factorize(const int &x) {
    int currentX = abs(x);
    if (isPrime(currentX) || currentX < 4) {
        return {{currentX, 1}};
    }
    std::unordered_map<int, int> primeFactors = {};
    while (currentX % 2 == 0) {
        if (primeFactors.find(2) != primeFactors.end()) {
            primeFactors[2]++;
        } else {
            primeFactors[2] = 1;
        }
        currentX /= 2;
    }

    for (int i = 3; i <= currentX; i += 2) {
        if (isPrime(i)) {
            while (currentX % i == 0) {
                if (primeFactors.find(i) != primeFactors.end()) {
                    primeFactors[i]++;
                } else {
                    primeFactors[i] = 1;
                }
                currentX /=  i;
            }
        }
    }

    return primeFactors;
}


int main() {
    int x;
    std::cout << "Enter a number: ";
    std::cin >> x;

    auto factors = prime_factorize(x);

    std::cout << x << " = ";
    for (auto p : factors) {
        std::cout << "(" << p.first << " ^ " << p.second << ")";
    }
}

Sample output:

Enter a number: 1238
1238 = (619 ^ 1)(2 ^ 1)

score 0 · Answer 2 · answered Oct 31 '19 at 14:02

To begin with, avoid using namespace std at the top of your program. Second, don't use function declarations when you can put your definitions before the use of those functions (but this may be a matter of preference).

When finding primes, I'd divide the number by 2, then by 3, and so on. I can also try with 4, but I'll never be able to divide by 4 if 2 was a divisor, so non primes are automatically skipped.

This is a possible solution:

#include <iostream>

int main(void)
{
    int n = 3 * 5 * 5 * 262417;

    bool first = true;
    int i = 2;
    int count = 0;
    while (i > 1) {
        if (n % i == 0) {
            n /= i;
            ++count;
        }
        else {
            if (count > 0) {
                if (!first)
                    std::cout << ", ";
                std::cout << i;
                if (count > 1)
                    std::cout << "^" << count;
                first = false;
                count = 0;
            }
            i++;
            if (i * i > n)
                i = n;
        }
    }
    std::cout << "\n";

    return 0;
}

Note the i * i > n which is an alternative to the sqrt() you are using.

Print prime factorization in exponential form in C++

2 Answers2