# 分解质因数
# 难度：简单
# 质因数的定义：
能整除给定正整数的质数。
百度百科：质因数
# 描述：
- 将一个整数分解为若干质因数之乘积
- 你需要从小到大排列质因子
# 样例：
- 给出
10, 返回[2, 5] - 给出
660, 返回[2, 2, 3, 5, 11]
# 题目分析：
从小到大排列质因子，需要将同一个质因子整除干净。
比如：20 可以被 2 整除两次。
提示：需要两层循环。
# 代码：
// 分解质因数
const primeFactorization = function(num) {
let res = [];
// 不需要判定i是否为质数，如果i不为质数，且能整除num时，num早被i的因数所除。故能整除num的i必是质数。
// i * i > num 退出循环 num一开始会在第二层循环被i整除成比较小的数字
for (let i = 2; i * i <= num; i++) {
while (num % i === 0) {
// 直到有余数退出循环
num = num / i; // 改变num
res.push(i); // 没有余数 能整除 这一步会找出所有质因数 不会出现4的那种情况
}
}
if (num !== 1) res.push(num); // num到最后也是质因数
return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15