c++中如何求一个数的质因数分解_c++质因数分解算法

试除法质因数分解高效易懂，枚举2到√n的因子，每次除尽并计数，剩余>1的n即为最大质因子；无需预筛质数，可优化为先判2再枚举奇数。

用试除法实现质因数分解（最常用、够快、易懂）

对大多数实际场景（比如 n ≤ 10^12），试除法足够高效且稳定。核心思路是从小到大枚举可能的质因子，每次把 n 中该因子全部除尽，同时记录次数。

关键点：只需枚举到 sqrt(n)，因为若 n 有大于 sqrt(n) 的质因子，最多只有一个——即最后剩下的那个 >1 的 n 值本身。

• 从 i = 2 开始循环，直到 i * i
• 若 n % i == 0，说明 i 是质因子，不断用 n /= i 并计数
• 循环结束后，若 n > 1，则它本身就是剩余的质因子（且只出现一次）

void prime_factorize(long long n) {     for (long long i = 2; i * i <= n; i++) {         if (n % i == 0) {             int cnt = 0;             while (n % i == 0) {                 n /= i;                 cnt++;             }             printf("%lld^%d ", i, cnt);         }     }     if (n > 1) printf("%lld^1", n); }

为什么不用先筛质数再试除？

除非你要对大量数字（如 10⁵ 个）做质因数分解，否则预筛质数（如埃氏筛）反而拖慢单次分解。原因：

• 筛到 sqrt(n) 需要 O(sqrt(n) log log sqrt(n)) 时间和空间，而试除法最坏也就 O(sqrt(n)) 时间，常数更小
• 筛出的质数数组可能很大（比如 n = 1e12 → 要筛到 1e6，质数约 8 万个），但实际能整除的因子极少
• 试除过程中遇到的合数（如 4、6、9）根本不会被 n % i == 0 触发，因为前面的质因子（2、3）已把它们的质因子全除掉了

处理大整数或需要多次调用时的优化方向

如果频繁分解（比如在线查询、密码学小规模场景），可考虑以下调整：

立即学习“C++免费学习笔记（深入）”；

• 先特判 2，然后只枚举奇数：i = 3, 5, 7, ...，减少一半迭代
• 对 n 做快速小因子预检（如用 int 类型先试除前 100 个质数），避免大数取模开销
• 若已知 n 是两个相近大质数乘积（如 RSA 模数），试除法失效，得换 Pollard-Rho 等随机算法——但这不属于常规需求

注意：long long 范围内，试除法在最坏情况（n 是两个大质数乘积，如 999999999989 * 999999999997）仍可能超时，此时需切换算法，但这种情况极少见。

常见错误：忘记 long long 溢出或忽略因子指数为 1 的输出

典型翻车点：

• i * i 中，若 i 和 n 都是 int，但 n 接近 INT_MAX，i * i 会溢出变成负数，导致死循环 → 必须统一用 long long
• 输出时只写 i 不写指数，或漏掉最后的 n > 1 分支，导致结果不完整
• 误以为 i 一定是质数——其实不需要判断，因为小因子早被除尽，能整除的 i 必然是质因子

边界输入如 n = 1 时，应无输出；n = 2 或 n = 997（大质数）时，必须输出最后一项。