效率翻倍用C‘筛选法’批量分解质因数LeetCode刷题利器在算法面试和编程竞赛中质因数分解是一个常见的基础问题。传统短除法虽然直观易懂但在处理大量查询时效率明显不足。本文将介绍一种基于预处理思想的筛选法通过构建最小质因数数组将单次分解的时间复杂度降至O(log N)特别适合LeetCode等平台上的批量质因数分解问题。1. 为什么需要更高效的质因数分解方法质因数分解在算法题中应用广泛从简单的数学问题到复杂的数论应用都可能涉及。比如计算最大公约数(GCD)、最小公倍数(LCM)、欧拉函数等都需要先进行质因数分解。传统短除法的时间复杂度是O(√N)这在单次查询时表现尚可。但在以下场景中就显得力不从心需要多次查询不同数字的质因数分解处理大范围内的连续数字分解竞赛中对时间效率要求极高的题目筛选法的核心优势在于它将计算分为两个阶段预处理阶段构建最小质因数数组O(N log log N)查询阶段每次分解只需O(log N)时间这种空间换时间的策略正是算法优化中常用的技巧。2. 最小质因数数组的构建原理筛选法的关键在于预处理阶段构建的最小质因数数组P[]。对于任意合数nP[n]存储的是n的最小质因数对于质数nP[n]为0。构建过程基于埃拉托斯特尼筛法埃氏筛的变种const int MAX 1e6; // 根据问题规模调整 int P[MAX1]; 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的质因数变得异常简单vectorint factorize(int n) { vectorint 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_mapint, 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_mapint, 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: vectorint 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; } } } } vectorint getPrimes(int n) { vectorint 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(vectorint nums) { int max_num *max_element(nums.begin(), nums.end()); buildSieve(max_num); // 并查集实现略... } };5. 性能优化与边界处理在实际应用中我们还需要考虑一些优化和边界情况内存优化对于大范围的预处理如1e8P数组会占用较多内存。可以使用位压缩或分段筛法来优化。范围调整预处理的范围应根据具体问题确定。如果已知查询数字的上限只需预处理到该上限即可。特殊数字处理0和1需要特殊处理负数的处理通常取其绝对值大质数的快速判断P[n]0多线程预处理对于超大范围的预处理可以考虑并行化筛法构建过程。// 带边界检查的分解函数 vectorint safeFactorize(int n) { if (n 2) return {}; vectorint 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; }筛选法分解质因数是算法工具箱中的一个实用技巧特别适合需要频繁进行质因数分解的场景。通过合理的预处理可以显著提升程序整体性能。掌握这种方法在面对相关算法问题时将更具优势。
效率翻倍！用C++‘筛选法’批量分解质因数，LeetCode刷题利器
效率翻倍用C‘筛选法’批量分解质因数LeetCode刷题利器在算法面试和编程竞赛中质因数分解是一个常见的基础问题。传统短除法虽然直观易懂但在处理大量查询时效率明显不足。本文将介绍一种基于预处理思想的筛选法通过构建最小质因数数组将单次分解的时间复杂度降至O(log N)特别适合LeetCode等平台上的批量质因数分解问题。1. 为什么需要更高效的质因数分解方法质因数分解在算法题中应用广泛从简单的数学问题到复杂的数论应用都可能涉及。比如计算最大公约数(GCD)、最小公倍数(LCM)、欧拉函数等都需要先进行质因数分解。传统短除法的时间复杂度是O(√N)这在单次查询时表现尚可。但在以下场景中就显得力不从心需要多次查询不同数字的质因数分解处理大范围内的连续数字分解竞赛中对时间效率要求极高的题目筛选法的核心优势在于它将计算分为两个阶段预处理阶段构建最小质因数数组O(N log log N)查询阶段每次分解只需O(log N)时间这种空间换时间的策略正是算法优化中常用的技巧。2. 最小质因数数组的构建原理筛选法的关键在于预处理阶段构建的最小质因数数组P[]。对于任意合数nP[n]存储的是n的最小质因数对于质数nP[n]为0。构建过程基于埃拉托斯特尼筛法埃氏筛的变种const int MAX 1e6; // 根据问题规模调整 int P[MAX1]; 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的质因数变得异常简单vectorint factorize(int n) { vectorint 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_mapint, 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_mapint, 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: vectorint 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; } } } } vectorint getPrimes(int n) { vectorint 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(vectorint nums) { int max_num *max_element(nums.begin(), nums.end()); buildSieve(max_num); // 并查集实现略... } };5. 性能优化与边界处理在实际应用中我们还需要考虑一些优化和边界情况内存优化对于大范围的预处理如1e8P数组会占用较多内存。可以使用位压缩或分段筛法来优化。范围调整预处理的范围应根据具体问题确定。如果已知查询数字的上限只需预处理到该上限即可。特殊数字处理0和1需要特殊处理负数的处理通常取其绝对值大质数的快速判断P[n]0多线程预处理对于超大范围的预处理可以考虑并行化筛法构建过程。// 带边界检查的分解函数 vectorint safeFactorize(int n) { if (n 2) return {}; vectorint 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; }筛选法分解质因数是算法工具箱中的一个实用技巧特别适合需要频繁进行质因数分解的场景。通过合理的预处理可以显著提升程序整体性能。掌握这种方法在面对相关算法问题时将更具优势。
