LeetCode 补充题 153. 整数的质因数分解
题目描述
[!green]
牛客原题： ✅ 补充题 153. 整数的质因数分解
给定正整数
n，将它分解为若干质数的乘积，按非降序返回这些质数，重复因子重复输出。当
n=1时，返回空列表。
示例 1：
输入：
n = 60
输出：[2,2,3,5]
解释：60=2×2×3×5，每个输出元素都是质数。
示例 2：
输入：
n = 13
输出：[13]
解释： 13 本身是质数。
提示：
-
1≤n≤2³¹−1。
题意分析
返回的是质因子列表，不是所有约数；同一个质因子出现几次就要输出几次。逐个除去已经找到的因子，可以把问题缩小到剩余商，并自然保持结果非降序。
解法：不断缩小余数的试除
核心思路
[!blue]
从
d = 2递增试除，只要n % d == 0就输出d并令n /= d，直到该因子被除尽。此时能整除余数的d必为质数：若它是合数，它的更小质因子应该已经在此前被除尽。只需检查
d <= n / d。若越过这一界限后余数仍大于 1，该余数不可能还有两个都大于平方根的因子，因此必为最后一个质因子，直接加入结果。用除法判断避免d * d溢出。每次成功除法保持“已输出因子的乘积乘当前余数”等于原数。输入 1 不进入试除且不追加余数，返回空列表。
解题步骤
- 从因子 2 开始试除。
- 能整除就重复记录并除去该因子，直到不再整除。
- 当 d>n/d 时停止，剩余 n>1 则追加为最后的质因子。
代码实现
class Solution {
public List<Integer> primeFactors(int n) {
List<Integer> out = new ArrayList<>();
for (int d = 2; d <= n / d; d++) {
while (n % d == 0) {
out.add(d);
n /= d;
}
}
if (n > 1) {
out.add(n);
}
return out;
}
}
func primeFactors(n int) []int {
out := []int{}
for d := 2; d <= n/d; d++ {
for n%d == 0 {
out = append(out, d)
n /= d
}
}
if n > 1 {
out = append(out, n)
}
return out
}
复杂度分析
- 时间复杂度：$O(\sqrt{n})$。
- 空间复杂度：除结果外额外空间 $O(1)$。
关键点总结
[!green]
试除结束后若余数仍是合数，它必有不超过平方根的因子，与此前试除完毕矛盾，所以剩余数必为素数。
易错点总结
[!yellow]
这不是列出全部约数，也不是枚举所有乘积分组；d≤n/d 避免平方判断溢出。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 650. 两个键的键盘 | 中等 | 最少复制粘贴次数等于质因数之和，本题直接输出包含重复重数的完整质因数列表。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！