c++中如何实现质因数分解_c++分解质因子的算法代码【实例】

因为sqrt(n)仅覆盖小于等于√n的因子，而n可能残留一个大于√n的质因数；应先除尽2，再从3开始每次+2试除，循环条件为i*i≤n，最后若n>1则其本身即为最大质因数。

为什么不能直接用 sqrt(n) 作为循环上限就结束？

很多初学者写质因数分解时，习惯写成 for (int i = 2; i ，然后认为循环完就结束了。但这是错的——如果 n 在循环结束后仍大于 1，那它本身就是一个没被除尽的质数（比如 n = 17，循环只到 4，最后剩的 17 就是质因子）。必须额外判断 n > 1 的情况。

如何避免重复试除和跳过合数？

质因数分解不需要判断 i 是否为质数。只要从小到大试除，第一个能整除 n 的 i 必然是质数（因为它的真因子早就在前面被试过了，且已把对应因子全部除尽）。所以只需：

• 先处理所有因子 2：用 while (n % 2 == 0) 不断除，输出或存入结果
• 再从 i = 3 开始，每次 i += 2（跳过偶数）
• 循环条件用 i * i 比 i 更安全（避免浮点误差和类型转换问题）

完整可运行的 C++ 实现（含重复因子输出）

#include 
#include 
using namespace std;
vector primeFactors(int n) {
vector factors;
// 处理因子 2
while (n % 2 == 0) {
factors.push_back(2);
n /= 2;
}
// 处理奇因子，从 3 开始
for (int i = 3; i * i <= n; i += 2) {
while (n % i == 0) {
factors.push_back(i);
n /= i;
}
}
// 如果剩余 n > 1，则它本身是质数
if (n > 1) {
factors.push_back(n);
}
return factors;
}
int main() {
int n = 60;
vector res = primeFactors(n);
cout << n << " = ";
for (int i = 0; i < res.size(); ++i) {
if (i > 0) cout << " × ";
cout << res[i];
}
cout << endl;
return 0;
}

输出：60 = 2 × 2 × 3 × 5

如果只要不同质因子（去重），怎么改？

只需在每次找到新因子时，只记录一次，而不是每次整除都 push。例如把 factors.push_back(i) 移到 while 外面，并确保同一 i 只加一次：

• 把 while (n % i == 0) { n /= i; } 留在内层，只做除法
• 外层加一句 factors.push_back(i)，放在 while 后面
• 注意：2 的处理也要同步改成只 push 一次

这种变体适合求欧拉函数、判断是否为 square-free 数等场景。实际用哪种，取决于你是否需要指数信息——而上面原始版本天然保留了每个质因子出现的次数，更通用。