分解质因数

难度:简单

质因数的定义:

能整除给定正整数的质数。

百度百科:质因数

描述:

  1. 将一个整数分解为若干质因数之乘积
  2. 你需要从小到大排列质因子

样例:

  • 给出 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
Last Updated: 9/23/2018, 4:55:09 PM