c++阶乘因子(yinzi)
时间: 2025-06-29 19:21:53 浏览: 3
### C++ 实现阶乘分解质因数算法
为了实现阶乘分解质因数,在C++中可以采用埃拉托斯特尼筛法预先筛选出一定范围内的所有素数,随后利用这些素数来分解给定整数N的阶乘(N!)。这种方法能够高效处理较大数值下的阶乘分解问题。
下面是一个具体的代码实例:
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e6 + 5;
bool is_prime[MAX_N];
int prime[MAX_N], cnt;
void sieve(int n) {
memset(is_prime, true, sizeof(is_prime));
is_prime[0] = is_prime[1] = false;
for (ll i = 2; i <= n; ++i) {
if (is_prime[i]) {
prime[cnt++] = i;
for (ll j = i * i; j <= n; j += i)
is_prime[j] = false;
}
}
}
map<int, int> factorize_factorial(int n) {
map<int, int> factors;
for (int i = 0; i < cnt && prime[i] <= n; ++i) {
int p = prime[i];
for (int k = n / p, t = 1; k >= 1; k /= p, ++t)
factors[p] += k;
}
return factors;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
sieve(MAX_N - 1); // 预先计算好所有的素数
auto result = factorize_factorial(N);
for (auto &[p, exp] : result)
cout << p << " " << exp << "\n";
return 0;
}
```
此程序首先通过`seive()`函数实现了埃氏筛法用于找出小于等于指定上限的所有素数[^3]。接着定义了`factorize_factorial()`函数用来接收一个正整数参数并返回其阶乘被完全分解后的各个质因子及其对应的指数值组成的映射表。最后在主函数里读取输入数据调用上述两个辅助函数完成最终的结果输出[^4]。
阅读全文
相关推荐












