试除法质因数分解高效易懂，枚举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（大质数）时，必须输出最后一项。
