质因数分解的实现
哪些公司问过
答案要点
- 从 2 开始试除,循环条件 i*i<=n,只需试到根号 n
- 能整除就反复除尽并记录因子,保证记录的因子都是质数
- 循环结束后 n>1 时,剩余的 n 是最后一个质因数
- 按格式用乘号连接输出,时间复杂度 O(√n)
- 边界:n 为 1、0、负数;大量查询可用筛法预处理最小质因子
易错点
- 循环结束后忘记处理剩余大于 1 的质因数
- 每个因子只除一次,漏掉重复的质因子
- 用 i<=n 作为循环条件,复杂度退化为 O(n)
面试官常见追问
- 为什么只需要试除到根号 n?
- 可以怎样进一步加速?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。