我在 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循环代替递归吗?
最佳答案
否。您的递归算法的工作时间与除数的数量完全相同。任何渐进速度更快的算法都无法打印所有这些数字。
是。任何递归算法都可以使用
std::stack
以非递归方式重写以存储局部变量。但是,在您的情况下,这可能不会更快,并且会使代码的可读性大大降低,因此这种重写是不可取的。如果需要,我可以提供代码。
关于c++ - 给定一个数字的质因数分解,在没有递归的情况下迭代 C++ 中的所有因子,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39077923/