质数

质数只能被 1 和它本身整除。一个数的因子是指能整除该数的所有正整数。

查找质数因子

例如，180 的质因子为 2、3、5。

function fn(num) {
  const arr = []
  for (i = 2; i < num; i++) {
    while (num % i === 0) {
      arr.push(i)
      num = num / i
    }
  }
  num !== 1 && arr.push(num)
  return arr
}

以上算法的时间复杂度为 O(n)O(n)，其中 nn 为输入正整数的大小。

优化：查找范围

只需要枚举从 2 到 i * i 的正整数即可，因为一个数的因子不可能超过它的平方。

function fn(num) {
  const arr = []
  for (i = 2; i < num; i++) { 
  for (i = 2; i * i <= num; i++) { 
    while (num % i === 0) {
      arr.push(i)
      num = num / i
    }
  }
  num !== 1 && arr.push(num)
  return arr
}