c++ - 给定一个数字的质因数分解，在没有递归的情况下迭代 C++ 中的所有因子

Question

我在 map 中给出了数字 p1^x1 * p2^x2 * .... 的质因数分解。我需要遍历它的所有因素，素数和合数。我设法使用递归编写了一个解决方案。

#include <iostream>
#include <map>
#include <cstdlib>

using namespace std;

struct PROBLEM {

    int mx = 400;
    map<int, int> mp = {{2, 2}, {3, 1},  {5, 1}, {7, 2}};
    int lastPrimeFactor = 7;
    int num = 1;

    auto solve() {
        rec(2, 0);
        return 0;
    }

    int next_prime_factor(int p) {
        return (p == 2) ? 3 : (p == 3) ? 5 : (p == 5) ? 7 : -1;
    }

    void rec(int prime, int power) {

        if (mx == 0) {
            cout << "Infinite recursion\n\n";
            exit(0);
        } else --mx;

        if (prime == lastPrimeFactor && power > mp[prime]) {
            return;
        }

        if (power < mp[prime]) {
            num *= prime;
            cout << num << endl;
            rec(prime,  power + 1);
            num /= prime;
        }

        if (prime != lastPrimeFactor) {
            rec(next_prime_factor(prime),  0);
        }

    }

};


int main() {
    PROBLEM().solve();
    return 0;
}

问题:

1) 有没有更快的方法来生成这些因子？

2)如果可能，我可以用while循环代替递归吗？

Answer 1

1. 否。您的递归算法的工作时间与除数的数量完全相同。任何渐进速度更快的算法都无法打印所有这些数字。

2. 是。任何递归算法都可以使用 std::stack 以非递归方式重写以存储局部变量。但是，在您的情况下，这可能不会更快，并且会使代码的可读性大大降低，因此这种重写是不可取的。如果需要，我可以提供代码。