c++ - 在C++中以指数形式打印素数分解

到目前为止，我已经有了这段代码。我正在尝试使用指数打印素因数分解。例如，如果我的输入为20，则输出应为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;
}

我希望有人可以帮助我。

最佳答案

您可以使用std::unordered_map<int, int>存储两个数字（对于x，n和x^n）。基本上，通常通过遍历小于数字本身的质数，将数字除以每个质数来尽可能多地遍历并记录除以的每个质数来正常分解该数。每次用质数p除时，将计数器加到map[p]。

我从我以前的一些旧代码中整理了一个示例实现。它要求一个数字并将其分解，并在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 << ")";
    }
}

样本输出：

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

关于c++ - 在C++中以指数形式打印素数分解，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58634395/