整数 N! 分解质因数：算法详解与 C++ 代码实现

问题分析 需要将 N! 分解质因数，并按质因数从小到大的顺序输出每个质因数的指数。 核心思路 N! 的质因数分解中，质数 p 的指数计算公式为： \[ e_p = \left\lfloor \frac{N}{p} \right\rfloor + \left\lfloor \frac{N}{p^2} \right\rfloor + \left\lfloor \frac{N}{p^3} \right\rfloor + \cdots \] 直到 \( p^k > N \)。 算法步骤 1. 使用筛法生成不超过 N 的所有质数。 2. 对每个质数 p，计算其在 N! 中的指数。 3. 按顺序输出 p 和对应的指数（指数大于 0 才输出）。 代码实现（C++） ```cpp #include <iostream> #include <vector> using namespace std; // 筛法生成质数表 vector<int> getPrimes(int n) { vector<bool> isPrime(n + 1, true); vector<int> primes; for (int i = 2; i <= n; ++i) { if (isPrime[i]) { primes.push_back(i); for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } return primes; } int main() { int N; cin >> N; vector<int> primes = getPrimes(N); for (int p : primes) { int count = 0; long long power = p; // 防止溢出 while (power <= N) { count += N / power; power *= p; } if (count > 0) { cout << p << " " << count << endl; } } return 0; } ``` 样例验证 输入： ``` 5 ``` 输出： ``` 2 3 3 1 5 1 ``` 与题目样例一致。 复杂度分析 - 时间复杂度：\( O(N \log \log N + \pi(N) \log N) \)，其中 \(\pi(N)\) 是小于等于 N 的质数个数。 - 空间复杂度：\( O(N) \)。 ######[AI问答 | 504点数解答 | 2026-01-12 17:42:36]