到O(√n)的算法优化与工程实践)
1. 项目概述为什么我们需要“快速”分解质因数在编程面试、算法竞赛如LeetCode、Codeforces或是处理某些加密、哈希算法的底层逻辑时分解质因数是一个绕不开的经典问题。题目要求很简单给定一个正整数n找出所有能整除n的质数并统计每个质数出现的次数。例如60 2^2 * 3^1 * 5^1。一个朴素的实现从2遍历到n逐个试除时间复杂度是O(n)对于稍大一点的数字比如10^9就完全不可行了。所以“快速”二字是核心。它不仅仅是一个功能实现更是对算法效率的极致追求。一个高效的质因数分解算法能将时间复杂度从O(n)优化到O(√n)甚至利用更高级的算法如Pollard‘s Rho处理更大的整数。在C中实现它不仅是对语言基础循环、条件、函数的检验更是对数学思维和算法优化能力的综合锻炼。无论是准备面试的“八股文”还是开发需要处理大数运算的实际项目比如简易的RSA加密演示掌握快速质因数分解都是一项硬核技能。2. 算法核心思路与选型分析实现快速分解质因数主流且实用的思路是试除法的优化版本。我们不会傻傻地试除每一个数而是利用数学性质大幅减少尝试的次数。2.1 基础试除法及其瓶颈最原始的方法是用i从2开始循环到n如果n能被i整除则i就是一个质因数我们让n不断除以i直到不能整除为止然后i继续。// 朴素方法 - 效率低下 vectorpairint, int factorize_naive(int n) { vectorpairint, int factors; // 存储质因数及其指数 for (int i 2; i n; i) { if (n % i 0) { int cnt 0; while (n % i 0) { n / i; cnt; } factors.emplace_back(i, cnt); } } return factors; }这个方法的瓶颈显而易见当n本身是一个大质数时循环要进行n次完全不可接受。2.2 优化一循环至 sqrt(n)关键洞察如果n有一个大于sqrt(n)的质因数p那么与之配对的另一个因数q n / p必然小于sqrt(n)。q会在之前的循环中被检测到并在整除过程中将n中的p也消除掉。因此我们只需要试除到sqrt(n)即可。循环结束后需要检查n是否大于1。如果大于1那么此时的n一定是最后一个大于原sqrt(n)的质因数且指数为1。// 优化一试除到 sqrt(n) vectorpairint, int factorize_sqrt(int n) { vectorpairint, int factors; for (int i 2; i * i n; i) { // 注意条件 i*i n 比 i sqrt(n) 更快 if (n % i 0) { int cnt 0; while (n % i 0) { n / i; cnt; } factors.emplace_back(i, cnt); } } if (n 1) { factors.emplace_back(n, 1); // 剩下的n是质数 } return factors; }这个优化将时间复杂度从O(n)降到了O(√n)是一个质的飞跃。对于n10^9最多只需循环大约31622次。2.3 优化二跳过偶数另一个明显的优化除了2以外所有质数都是奇数。所以在处理完2之后我们可以从3开始每次循环i 2只检查奇数。// 优化二处理2后跳过偶数 vectorpairint, int factorize_skip_even(int n) { vectorpairint, int factors; // 处理质因数2 if (n % 2 0) { int cnt 0; while (n % 2 0) { n / 2; cnt; } factors.emplace_back(2, cnt); } // 从3开始只检查奇数 for (int i 3; i * i n; i 2) { if (n % i 0) { int cnt 0; while (n % i 0) { n / i; cnt; } factors.emplace_back(i, cnt); } } if (n 1) { factors.emplace_back(n, 1); } return factors; }这个优化大约能减少一半的循环次数。对于主要质因数为奇数的数效果显著。2.4 算法选型总结对于绝大多数编程场景面试、竞赛、常规软件开发优化二试除至√n并跳过偶数已经完全够用它实现了效率与代码复杂度的最佳平衡。更高级的算法如Pollard‘s Rho算法虽然对超大的合数比如超过10^18有更好的期望时间复杂度但其实现复杂且在小整数上优势不明显通常只在专门的数论库或处理密码学问题时才会用到。因此本项目将聚焦于实现并深度优化这个“优化二”版本的试除法。3. 核心细节解析与实操要点理解了核心算法我们来看看实现中的关键细节和容易踩坑的地方。3.1 数据类型的正确选择这是第一个坑。题目通常只说“正整数n”但范围呢如果n可能接近int的上限约21亿那么在循环条件i * i n中i * i可能会溢出导致未定义行为或无限循环。解决方案使用更宽的类型将循环变量i和中间计算提升到long long。改变循环条件将i * i n改为i n / i。后者在数学上是等价的但避免了乘法溢出因为除法运算会先发生。// 更安全的循环条件防止int溢出 for (long long i 3; i n / i; i 2) { // ... 操作 }或者如果确定n的范围在int内且i不会太大导致i*i溢出也可以保持原样。但在工业级代码中使用i n / i是更稳健的做法。3.2 质因数判定的隐含逻辑我们的循环中i并不总是质数比如i9时。那为什么还能正确分解呢这是因为合数i的质因数一定小于i。例如当i9合数时它的质因数3已经在i3时被从n中除尽了所以当i增长到9时n必然不能被9整除。因此凡是能进入if (n % i 0)分支的i此时一定是质数。这是一个非常巧妙且重要的性质它让我们无需额外编写质数判断函数。3.3 结果存储与输出格式我们使用vectorpairint, int来存储结果其中pair.first是质因数pair.second是指数。这种结构清晰且易于后续处理。输出时通常需要格式化例如输出2^2 * 3^1 * 5^1。void printFactors(const vectorpairint, int factors) { bool first true; for (const auto [prime, exp] : factors) { if (!first) cout * ; cout prime; if (exp 1) cout ^ exp; first false; } cout endl; }注意在C17及以上版本可以使用结构化绑定[prime, exp]代码更简洁。如果编译器不支持需使用p.first和p.second。4. 完整实现与性能实测下面给出一个完整的、健壮的C实现包含详细的注释和错误处理。#include iostream #include vector #include utility // for std::pair #include cmath // 虽然我们不用sqrt但留着以备其他用途 using namespace std; /** * brief 快速分解正整数n的质因数 * param n 待分解的正整数要求 n 1 * return 一个向量每个元素是一个pair质因数, 指数 */ vectorpairlong long, int fastPrimeFactorization(long long n) { vectorpairlong long, int factors; if (n 1) { // 对于1或小于1的数返回空结果或者可以抛出异常 // 这里根据题目要求1通常被认为没有质因数 return factors; } // 阶段一处理质因数2 if (n % 2 0) { int cnt 0; while (n % 2 0) { n / 2; cnt; } factors.emplace_back(2, cnt); } // 阶段二处理奇数因子 // 使用 long long 防止 i*i 溢出使用 i n/i 作为条件更安全 for (long long i 3; i n / i; i 2) { if (n % i 0) { int cnt 0; while (n % i 0) { n / i; cnt; } factors.emplace_back(i, cnt); } } // 阶段三处理剩余的质数 if (n 1) { // 此时n一定是质数 factors.emplace_back(n, 1); } return factors; } /** * brief 格式化输出质因数分解结果 */ void printFactorization(const vectorpairlong long, int factors) { if (factors.empty()) { cout 1 没有质因数。 endl; return; } bool isFirst true; for (const auto [prime, exponent] : factors) { if (!isFirst) { cout * ; } cout prime; if (exponent 1) { cout ^ exponent; } isFirst false; } cout endl; } int main() { long long num; cout 请输入一个正整数: ; cin num; if (num 0) { cerr 错误请输入一个正整数。 endl; return 1; } auto factors fastPrimeFactorization(num); cout num ; printFactorization(factors); // 可选详细输出 cout \n详细分解 endl; for (const auto [prime, exponent] : factors) { cout 质因数 prime , 指数 exponent endl; } return 0; }性能实测与分析 我们来测试几个典型值感受一下“快速”的含义。假设在普通PC上单次操作纳秒级。n 60循环到sqrt(60)≈7且跳过偶数后实际检查i3,5,7几乎瞬间完成。n 999983一个6位质数朴素方法需循环近100万次。我们的优化方法循环到sqrt(999983)≈999且只检查奇数大约500次循环。速度相差约2000倍。n 2147483647即2^31-1是一个著名的梅森质数这是int范围内的最大质数。优化方法循环到sqrt(n)≈46340检查奇数约23170次。虽然次数不少但在现代计算机上仍是毫秒级别。朴素方法则要循环21亿次完全不可行。5. 边界条件与异常处理一个健壮的程序必须考虑各种边界和异常输入。输入n 1根据数学定义1没有质因数0和负整数则不属于质因数分解的讨论范围。我们的函数应返回空向量并在主函数中进行友好提示。大数溢出如前所述使用long long并采用i n / i的判断条件可以有效防止在计算循环条件时溢出。输入非数字在main函数中cin输入失败会导致流状态错误。可以增加检查if (!(cin num)) { cerr “错误请输入一个有效的整数。” endl; cin.clear(); // 清除错误状态 cin.ignore(numeric_limitsstreamsize::max(), ‘\n’); // 忽略错误输入 return 1; }结果去重与排序我们的算法保证了质因数是从小到大发现的并且因为合数不会被误判所以结果自然就是有序且无重复的(质因数指数)对。6. 进阶探讨与优化极限虽然“试除至√n并跳过偶数”已经很快但我们还能再压榨一点性能吗可以但代码会变得更复杂。6.1 预生成质数表我们可以预先用筛法如埃拉托斯特尼筛法生成一个从3到sqrt(MAX_N)的质数表。在分解时不再用i2循环所有奇数而是直接遍历这个质数表。这样避免了检查像9、15、21这样的合数奇数。// 假设我们已经有了一个质数表 primes包含3, 5, 7, 11, ... for (long long p : primes) { if (p n / p) break; // 等价于 p*p n if (n % p 0) { int cnt 0; while (n % p 0) { n / p; cnt; } factors.emplace_back(p, cnt); } }这种方法在需要多次分解不同数字的场景下如解决一个包含多个询问的问题优势巨大因为质数表只需生成一次。但对于单次分解生成质数表本身也有开销可能得不偿失。6.2 使用更快的质数判别法在试除循环中我们依赖“合数不会被整除”的性质。如果我们能提前知道某个i是合数并跳过它也能节省时间。但这通常需要额外的判断逻辑如查表或快速质数测试其开销可能比直接做一次取模运算还大对于int范围内的数通常不划算。6.3 何时需要Pollard‘s Rho算法当n的范围超过10^12甚至达到10^18时O(√n)的试除法也将变得缓慢。Pollard‘s Rho算法是一种概率性算法其期望时间复杂度约为O(n^(1/4))对于大合数要快得多。它的核心思想是利用生日悖论和Floyd判环算法来寻找n的一个非平凡因子。实现它需要用到快速乘防止溢出、快速幂取模和GCD算法代码复杂度陡增。除非你确定要处理非常大的整数否则试除法优化版足矣。7. 常见问题与调试技巧在实际编写和运行过程中你可能会遇到以下问题程序对某些数陷入死循环或输出错误检查循环条件最可能的原因是i * i n在i较大时溢出变成了负数或0导致条件永远成立。务必使用i n / i。检查输入和类型确保n和循环变量i的类型足够宽long long。验证特殊输入测试n1,n2,n3,n4,n一个大质数n一个完全平方数如49。结果中出现了合数这几乎不可能发生除非你的算法逻辑有误。回顾3.2节的原理确保你在找到因子i后使用while循环将n中所有该因子除尽。性能不如预期对于极大的n如10^12以上试除法本身就会慢。这是算法复杂度决定的。使用-O2或-O3编译优化选项可以显著提升速度。在多次查询的场景下务必使用预生成质数表的方案。如何验证结果的正确性写一个简单的验证函数将分解结果乘回去看是否等于原数。bool verifyFactorization(long long n, const vectorpairlong long, int factors) { long long product 1; for (const auto [p, e]) { for (int i 0; i e; i) product * p; } return product n; }在在线判题系统OJ中应注意什么输入输出效率如果输入量巨大使用scanf/printf或关闭cin/cout同步流ios::sync_with_stdio(false); cin.tie(nullptr);。空间复杂度我们的算法只使用了少量变量和一个结果向量空间是O(1)的不算输出完全不用担心。时间复杂度明确题目中n的范围。如果n 10^9O(√n)的试除法是安全的。如果n 10^12可能需要更精细的常数优化。如果更大就得考虑Pollard‘s Rho了。8. 项目扩展与应用场景掌握了核心的质因数分解函数你可以轻松将其融入更大的项目中计算最大公约数GCD和最小公倍数LCM将两个数分别分解质因数对于每个质因数取指数的最小值得到GCD的因子取指数的最大值得到LCM的因子。计算正约数个数若n p1^a1 * p2^a2 * ... * pk^ak则n的正约数个数为(a11)*(a21)*...*(ak1)。计算欧拉函数Euler‘s Totient Function用于RSA加密等。φ(n) n * Π(1 - 1/p)其中p取遍n的所有质因数。解决特定数学问题如判断一个数是否为“丑数”质因数只包含2,3,5或者判断一个数是否可以被表示为某个质数的幂。简易的RSA加密演示RSA的核心在于选择两个大质数p和q。虽然我们无法生成真正安全的大质数但可以用这个分解函数来演示“破解”小密钥的过程即已知公钥np*q尝试分解出p和q。最后分享一个我调试时的小技巧对于不确定的算法不要只用一个数测试。写一个从1到10000或更大的循环用你的快速分解函数和一种绝对正确但很慢的朴素分解函数比如对每个因子从2试除到它本身同时计算并对比结果。只有当成千上万个测试用例都通过时你才能对代码的正确性有足够的信心。这种“对拍”是算法竞赛和严谨开发中非常实用的方法。
1. 项目概述为什么我们需要“快速”分解质因数在编程面试、算法竞赛如LeetCode、Codeforces或是处理某些加密、哈希算法的底层逻辑时分解质因数是一个绕不开的经典问题。题目要求很简单给定一个正整数n找出所有能整除n的质数并统计每个质数出现的次数。例如60 2^2 * 3^1 * 5^1。一个朴素的实现从2遍历到n逐个试除时间复杂度是O(n)对于稍大一点的数字比如10^9就完全不可行了。所以“快速”二字是核心。它不仅仅是一个功能实现更是对算法效率的极致追求。一个高效的质因数分解算法能将时间复杂度从O(n)优化到O(√n)甚至利用更高级的算法如Pollard‘s Rho处理更大的整数。在C中实现它不仅是对语言基础循环、条件、函数的检验更是对数学思维和算法优化能力的综合锻炼。无论是准备面试的“八股文”还是开发需要处理大数运算的实际项目比如简易的RSA加密演示掌握快速质因数分解都是一项硬核技能。2. 算法核心思路与选型分析实现快速分解质因数主流且实用的思路是试除法的优化版本。我们不会傻傻地试除每一个数而是利用数学性质大幅减少尝试的次数。2.1 基础试除法及其瓶颈最原始的方法是用i从2开始循环到n如果n能被i整除则i就是一个质因数我们让n不断除以i直到不能整除为止然后i继续。// 朴素方法 - 效率低下 vectorpairint, int factorize_naive(int n) { vectorpairint, int factors; // 存储质因数及其指数 for (int i 2; i n; i) { if (n % i 0) { int cnt 0; while (n % i 0) { n / i; cnt; } factors.emplace_back(i, cnt); } } return factors; }这个方法的瓶颈显而易见当n本身是一个大质数时循环要进行n次完全不可接受。2.2 优化一循环至 sqrt(n)关键洞察如果n有一个大于sqrt(n)的质因数p那么与之配对的另一个因数q n / p必然小于sqrt(n)。q会在之前的循环中被检测到并在整除过程中将n中的p也消除掉。因此我们只需要试除到sqrt(n)即可。循环结束后需要检查n是否大于1。如果大于1那么此时的n一定是最后一个大于原sqrt(n)的质因数且指数为1。// 优化一试除到 sqrt(n) vectorpairint, int factorize_sqrt(int n) { vectorpairint, int factors; for (int i 2; i * i n; i) { // 注意条件 i*i n 比 i sqrt(n) 更快 if (n % i 0) { int cnt 0; while (n % i 0) { n / i; cnt; } factors.emplace_back(i, cnt); } } if (n 1) { factors.emplace_back(n, 1); // 剩下的n是质数 } return factors; }这个优化将时间复杂度从O(n)降到了O(√n)是一个质的飞跃。对于n10^9最多只需循环大约31622次。2.3 优化二跳过偶数另一个明显的优化除了2以外所有质数都是奇数。所以在处理完2之后我们可以从3开始每次循环i 2只检查奇数。// 优化二处理2后跳过偶数 vectorpairint, int factorize_skip_even(int n) { vectorpairint, int factors; // 处理质因数2 if (n % 2 0) { int cnt 0; while (n % 2 0) { n / 2; cnt; } factors.emplace_back(2, cnt); } // 从3开始只检查奇数 for (int i 3; i * i n; i 2) { if (n % i 0) { int cnt 0; while (n % i 0) { n / i; cnt; } factors.emplace_back(i, cnt); } } if (n 1) { factors.emplace_back(n, 1); } return factors; }这个优化大约能减少一半的循环次数。对于主要质因数为奇数的数效果显著。2.4 算法选型总结对于绝大多数编程场景面试、竞赛、常规软件开发优化二试除至√n并跳过偶数已经完全够用它实现了效率与代码复杂度的最佳平衡。更高级的算法如Pollard‘s Rho算法虽然对超大的合数比如超过10^18有更好的期望时间复杂度但其实现复杂且在小整数上优势不明显通常只在专门的数论库或处理密码学问题时才会用到。因此本项目将聚焦于实现并深度优化这个“优化二”版本的试除法。3. 核心细节解析与实操要点理解了核心算法我们来看看实现中的关键细节和容易踩坑的地方。3.1 数据类型的正确选择这是第一个坑。题目通常只说“正整数n”但范围呢如果n可能接近int的上限约21亿那么在循环条件i * i n中i * i可能会溢出导致未定义行为或无限循环。解决方案使用更宽的类型将循环变量i和中间计算提升到long long。改变循环条件将i * i n改为i n / i。后者在数学上是等价的但避免了乘法溢出因为除法运算会先发生。// 更安全的循环条件防止int溢出 for (long long i 3; i n / i; i 2) { // ... 操作 }或者如果确定n的范围在int内且i不会太大导致i*i溢出也可以保持原样。但在工业级代码中使用i n / i是更稳健的做法。3.2 质因数判定的隐含逻辑我们的循环中i并不总是质数比如i9时。那为什么还能正确分解呢这是因为合数i的质因数一定小于i。例如当i9合数时它的质因数3已经在i3时被从n中除尽了所以当i增长到9时n必然不能被9整除。因此凡是能进入if (n % i 0)分支的i此时一定是质数。这是一个非常巧妙且重要的性质它让我们无需额外编写质数判断函数。3.3 结果存储与输出格式我们使用vectorpairint, int来存储结果其中pair.first是质因数pair.second是指数。这种结构清晰且易于后续处理。输出时通常需要格式化例如输出2^2 * 3^1 * 5^1。void printFactors(const vectorpairint, int factors) { bool first true; for (const auto [prime, exp] : factors) { if (!first) cout * ; cout prime; if (exp 1) cout ^ exp; first false; } cout endl; }注意在C17及以上版本可以使用结构化绑定[prime, exp]代码更简洁。如果编译器不支持需使用p.first和p.second。4. 完整实现与性能实测下面给出一个完整的、健壮的C实现包含详细的注释和错误处理。#include iostream #include vector #include utility // for std::pair #include cmath // 虽然我们不用sqrt但留着以备其他用途 using namespace std; /** * brief 快速分解正整数n的质因数 * param n 待分解的正整数要求 n 1 * return 一个向量每个元素是一个pair质因数, 指数 */ vectorpairlong long, int fastPrimeFactorization(long long n) { vectorpairlong long, int factors; if (n 1) { // 对于1或小于1的数返回空结果或者可以抛出异常 // 这里根据题目要求1通常被认为没有质因数 return factors; } // 阶段一处理质因数2 if (n % 2 0) { int cnt 0; while (n % 2 0) { n / 2; cnt; } factors.emplace_back(2, cnt); } // 阶段二处理奇数因子 // 使用 long long 防止 i*i 溢出使用 i n/i 作为条件更安全 for (long long i 3; i n / i; i 2) { if (n % i 0) { int cnt 0; while (n % i 0) { n / i; cnt; } factors.emplace_back(i, cnt); } } // 阶段三处理剩余的质数 if (n 1) { // 此时n一定是质数 factors.emplace_back(n, 1); } return factors; } /** * brief 格式化输出质因数分解结果 */ void printFactorization(const vectorpairlong long, int factors) { if (factors.empty()) { cout 1 没有质因数。 endl; return; } bool isFirst true; for (const auto [prime, exponent] : factors) { if (!isFirst) { cout * ; } cout prime; if (exponent 1) { cout ^ exponent; } isFirst false; } cout endl; } int main() { long long num; cout 请输入一个正整数: ; cin num; if (num 0) { cerr 错误请输入一个正整数。 endl; return 1; } auto factors fastPrimeFactorization(num); cout num ; printFactorization(factors); // 可选详细输出 cout \n详细分解 endl; for (const auto [prime, exponent] : factors) { cout 质因数 prime , 指数 exponent endl; } return 0; }性能实测与分析 我们来测试几个典型值感受一下“快速”的含义。假设在普通PC上单次操作纳秒级。n 60循环到sqrt(60)≈7且跳过偶数后实际检查i3,5,7几乎瞬间完成。n 999983一个6位质数朴素方法需循环近100万次。我们的优化方法循环到sqrt(999983)≈999且只检查奇数大约500次循环。速度相差约2000倍。n 2147483647即2^31-1是一个著名的梅森质数这是int范围内的最大质数。优化方法循环到sqrt(n)≈46340检查奇数约23170次。虽然次数不少但在现代计算机上仍是毫秒级别。朴素方法则要循环21亿次完全不可行。5. 边界条件与异常处理一个健壮的程序必须考虑各种边界和异常输入。输入n 1根据数学定义1没有质因数0和负整数则不属于质因数分解的讨论范围。我们的函数应返回空向量并在主函数中进行友好提示。大数溢出如前所述使用long long并采用i n / i的判断条件可以有效防止在计算循环条件时溢出。输入非数字在main函数中cin输入失败会导致流状态错误。可以增加检查if (!(cin num)) { cerr “错误请输入一个有效的整数。” endl; cin.clear(); // 清除错误状态 cin.ignore(numeric_limitsstreamsize::max(), ‘\n’); // 忽略错误输入 return 1; }结果去重与排序我们的算法保证了质因数是从小到大发现的并且因为合数不会被误判所以结果自然就是有序且无重复的(质因数指数)对。6. 进阶探讨与优化极限虽然“试除至√n并跳过偶数”已经很快但我们还能再压榨一点性能吗可以但代码会变得更复杂。6.1 预生成质数表我们可以预先用筛法如埃拉托斯特尼筛法生成一个从3到sqrt(MAX_N)的质数表。在分解时不再用i2循环所有奇数而是直接遍历这个质数表。这样避免了检查像9、15、21这样的合数奇数。// 假设我们已经有了一个质数表 primes包含3, 5, 7, 11, ... for (long long p : primes) { if (p n / p) break; // 等价于 p*p n if (n % p 0) { int cnt 0; while (n % p 0) { n / p; cnt; } factors.emplace_back(p, cnt); } }这种方法在需要多次分解不同数字的场景下如解决一个包含多个询问的问题优势巨大因为质数表只需生成一次。但对于单次分解生成质数表本身也有开销可能得不偿失。6.2 使用更快的质数判别法在试除循环中我们依赖“合数不会被整除”的性质。如果我们能提前知道某个i是合数并跳过它也能节省时间。但这通常需要额外的判断逻辑如查表或快速质数测试其开销可能比直接做一次取模运算还大对于int范围内的数通常不划算。6.3 何时需要Pollard‘s Rho算法当n的范围超过10^12甚至达到10^18时O(√n)的试除法也将变得缓慢。Pollard‘s Rho算法是一种概率性算法其期望时间复杂度约为O(n^(1/4))对于大合数要快得多。它的核心思想是利用生日悖论和Floyd判环算法来寻找n的一个非平凡因子。实现它需要用到快速乘防止溢出、快速幂取模和GCD算法代码复杂度陡增。除非你确定要处理非常大的整数否则试除法优化版足矣。7. 常见问题与调试技巧在实际编写和运行过程中你可能会遇到以下问题程序对某些数陷入死循环或输出错误检查循环条件最可能的原因是i * i n在i较大时溢出变成了负数或0导致条件永远成立。务必使用i n / i。检查输入和类型确保n和循环变量i的类型足够宽long long。验证特殊输入测试n1,n2,n3,n4,n一个大质数n一个完全平方数如49。结果中出现了合数这几乎不可能发生除非你的算法逻辑有误。回顾3.2节的原理确保你在找到因子i后使用while循环将n中所有该因子除尽。性能不如预期对于极大的n如10^12以上试除法本身就会慢。这是算法复杂度决定的。使用-O2或-O3编译优化选项可以显著提升速度。在多次查询的场景下务必使用预生成质数表的方案。如何验证结果的正确性写一个简单的验证函数将分解结果乘回去看是否等于原数。bool verifyFactorization(long long n, const vectorpairlong long, int factors) { long long product 1; for (const auto [p, e]) { for (int i 0; i e; i) product * p; } return product n; }在在线判题系统OJ中应注意什么输入输出效率如果输入量巨大使用scanf/printf或关闭cin/cout同步流ios::sync_with_stdio(false); cin.tie(nullptr);。空间复杂度我们的算法只使用了少量变量和一个结果向量空间是O(1)的不算输出完全不用担心。时间复杂度明确题目中n的范围。如果n 10^9O(√n)的试除法是安全的。如果n 10^12可能需要更精细的常数优化。如果更大就得考虑Pollard‘s Rho了。8. 项目扩展与应用场景掌握了核心的质因数分解函数你可以轻松将其融入更大的项目中计算最大公约数GCD和最小公倍数LCM将两个数分别分解质因数对于每个质因数取指数的最小值得到GCD的因子取指数的最大值得到LCM的因子。计算正约数个数若n p1^a1 * p2^a2 * ... * pk^ak则n的正约数个数为(a11)*(a21)*...*(ak1)。计算欧拉函数Euler‘s Totient Function用于RSA加密等。φ(n) n * Π(1 - 1/p)其中p取遍n的所有质因数。解决特定数学问题如判断一个数是否为“丑数”质因数只包含2,3,5或者判断一个数是否可以被表示为某个质数的幂。简易的RSA加密演示RSA的核心在于选择两个大质数p和q。虽然我们无法生成真正安全的大质数但可以用这个分解函数来演示“破解”小密钥的过程即已知公钥np*q尝试分解出p和q。最后分享一个我调试时的小技巧对于不确定的算法不要只用一个数测试。写一个从1到10000或更大的循环用你的快速分解函数和一种绝对正确但很慢的朴素分解函数比如对每个因子从2试除到它本身同时计算并对比结果。只有当成千上万个测试用例都通过时你才能对代码的正确性有足够的信心。这种“对拍”是算法竞赛和严谨开发中非常实用的方法。
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
