效率翻倍！用C++‘筛选法’批量分解质因数，LeetCode刷题利器
效率翻倍！用C++‘筛选法’批量分解质因数，LeetCode刷题利器
在算法面试和编程竞赛中，质因数分解是一个常见的基础问题。传统短除法虽然直观易懂，但在处理大量查询时效率明显不足。本文将介绍一种基于预处理思想的"筛选法"，通过构建最小质因数数组，将单次分解的时间复杂度降至O(log N)，特别适合LeetCode等平台上的批量质因数分解问题。
1. 为什么需要更高效的质因数分解方法？
质因数分解在算法题中应用广泛，从简单的数学问题到复杂的数论应用都可能涉及。比如计算最大公约数(GCD)、最小公倍数(LCM)、欧拉函数等，都需要先进行质因数分解。
传统短除法的时间复杂度是O(√N)，这在单次查询时表现尚可。但在以下场景中就显得力不从心：
- 需要多次查询不同数字的质因数分解
- 处理大范围内的连续数字分解
- 竞赛中对时间效率要求极高的题目
筛选法的核心优势在于它将计算分为两个阶段：
- 预处理阶段：构建最小质因数数组（O(N log log N)）
- 查询阶段：每次分解只需O(log N)时间
这种"空间换时间"的策略，正是算法优化中常用的技巧。
2. 最小质因数数组的构建原理
筛选法的关键在于预处理阶段构建的最小质因数数组P[]。对于任意合数n，P[n]存储的是n的最小质因数；对于质数n，P[n]为0。
构建过程基于埃拉托斯特尼筛法（埃氏筛）的变种：
const int MAX = 1e6; // 根据问题规模调整 int P[MAX+1]; void buildSieve() { for (int i = 2; i*i <= MAX; i++) { if (P[i] == 0) { // i是质数 for (int j = i*i; j <= MAX; j += i) { if (P[j] == 0) P[j] = i; // 标记j的最小质因数 } } } }这段代码做了以下工作：
- 初始化P数组全为0
- 从2开始遍历，如果P[i]为0，说明i是质数
- 对于每个质数i，标记i的所有倍数j的最小质因数为i
优化点：
- 内层循环从ii开始，而不是2i，因为更小的倍数已经被更小的质数处理过
- 只遍历到√MAX，因为更大的数的倍数会超出范围
3. 利用P数组高效分解质因数
有了P数组后，分解任意数n的质因数变得异常简单：
vector<int> factorize(int n) { vector<int> factors; while (P[n] != 0) { // 当n是合数时继续分解 factors.push_back(P[n]); n /= P[n]; } if (n > 1) factors.push_back(n); // 最后剩下的质数 return factors; }这个过程的时间复杂度是O(k)，其中k是n的质因数个数（包括重复）。由于一个数n最多有log₂n个质因数（当n是2的幂时），所以最坏情况下是O(log n)。
与传统方法的对比：
| 方法 | 预处理时间 | 单次查询时间 | 适用场景 |
|---|---|---|---|
| 短除法 | 无 | O(√n) | 单次或少次查询 |
| 筛选法 | O(n log log n) | O(log n) | 多次或批量查询 |
4. 实际应用案例
4.1 计算最大公约数(GCD)
虽然计算GCD有更高效的欧几里得算法，但质因数分解法在某些特殊问题中仍有优势：
int gcd(int a, int b) { auto fa = factorize(a); auto fb = factorize(b); unordered_map<int, int> count; for (int p : fa) count[p]++; int result = 1; for (int p : fb) { if (count[p] > 0) { result *= p; count[p]--; } } return result; }4.2 计算欧拉函数
欧拉函数φ(n)表示小于n且与n互质的正整数的个数，其计算依赖于质因数分解：
int eulerPhi(int n) { if (n == 1) return 1; auto factors = factorize(n); unordered_map<int, int> primeCount; for (int p : factors) primeCount[p]++; int result = n; for (auto [p, cnt] : primeCount) { result = result / p * (p - 1); } return result; }4.3 LeetCode真题应用
题目：952. Largest Component Size by Common Factor
这道题需要将共享至少一个公因数大于1的数字连接起来，求最大连通分量的大小。使用筛选法预处理最小质因数可以高效解决问题：
class Solution { public: vector<int> P; void buildSieve(int max_num) { P.resize(max_num + 1); for (int i = 2; i*i <= max_num; i++) { if (P[i] == 0) { for (int j = i*i; j <= max_num; j += i) { if (P[j] == 0) P[j] = i; } } } } vector<int> getPrimes(int n) { vector<int> primes; if (n == 1) return primes; while (P[n] != 0) { primes.push_back(P[n]); int p = P[n]; while (n % p == 0) n /= p; } if (n > 1) primes.push_back(n); return primes; } int largestComponentSize(vector<int>& nums) { int max_num = *max_element(nums.begin(), nums.end()); buildSieve(max_num); // 并查集实现略... } };5. 性能优化与边界处理
在实际应用中，我们还需要考虑一些优化和边界情况：
内存优化：对于大范围的预处理（如1e8），P数组会占用较多内存。可以使用位压缩或分段筛法来优化。
范围调整：预处理的范围应根据具体问题确定。如果已知查询数字的上限，只需预处理到该上限即可。
特殊数字处理：
- 0和1需要特殊处理
- 负数的处理（通常取其绝对值）
- 大质数的快速判断（P[n]==0）
多线程预处理：对于超大范围的预处理，可以考虑并行化筛法构建过程。
// 带边界检查的分解函数 vector<int> safeFactorize(int n) { if (n < 2) return {}; vector<int> factors; if (P.size() <= n) { // 如果超出预处理范围，回退到试除法 int temp = n; for (int i = 2; i*i <= temp; i++) { while (temp % i == 0) { factors.push_back(i); temp /= i; } } if (temp > 1) factors.push_back(temp); } else { while (P[n] != 0) { factors.push_back(P[n]); n /= P[n]; } if (n > 1) factors.push_back(n); } return factors; }筛选法分解质因数是算法工具箱中的一个实用技巧，特别适合需要频繁进行质因数分解的场景。通过合理的预处理，可以显著提升程序整体性能。掌握这种方法，在面对相关算法问题时将更具优势。