C++实现N!的质因子分解

以下是基于描述的算法的C++实现： ```cpp #include <iostream> #include <vector> using namespace std; // Function to perform prime factorization of N! void primeFactorization(int N) { // Step 1: Build a list of prime numbers up to N vector<int> primes; vector<bool> isPrime(N + 1, true); for (int i = 2; i <= N; ++i) { if (isPrime[i]) { primes.push_back(i); for (int j = i * 2; j <= N; j += i) { isPrime[j] = false; } } } // Step 2: Initialize count for each prime number to 0 vector<int> counts(primes.size(), 0); // Step 3: Iterate through each prime number for (int i = 0; i < primes.size(); ++i) { int p = primes[i]; // Step 3.1: Store the prime number cout << p << "^"; // Step 3.2: Divide N by the prime number and update counts int temp = N; while (temp >= p) { counts[i] += temp / p; temp /= p; } // Step 3.3: Check if the prime number exceeds N if (temp == 0) { cout << counts[i] << endl; break; } // Step 3.4: Move to the next prime number cout << counts[i] << " * "; } } int main() { int N; cout << "Enter a number N: "; cin >> N; cout << "Prime factorization of " << N << "!:" << endl; primeFactorization(N); return 0; } ``` 这段代码实现了对N!进行质因子分解的算法描述。它首先构建了从2到N的所有质数的列表，然后对每个质数进行质因子分解，并输出结果。