分解质因素的算法很难，理解不了。 请问有哪位大佬可以进行解释一下呢？

Question

分解质因素的算法很难，理解不了。

请问有哪位大佬可以进行解释一下呢？

功能:输入一个正整数，按照从小到大的顺序输出它的所有质因子（重复的也要列举）（如180的质因子为2 2 3 3 5 ）

Answer 1

首先你需要一个质数表\( 2, 3, 5, 7 \dots \)

依次用这些质数试除 180，直到为 1

180 / 2 = 90

对 90 执行同样的步骤

90 / 2 = 45

45 / 2 ❌

45 / 3 = 15

15 / 2 ❌

15 / 3 = 5

5 / 2 ❌

5 / 3 ❌

5 / 5 = 1

得到分解 2 2 3 3 5

---

let maxPrime = 1 // 质数集合中最大的质数
const primeNumbers = new Set<number>() // 质数集合

/**
 * 返回小于等于 max 的质数
 */
function generatePrimes(max: number) {
  if (maxPrime < max) {
    for (let i = maxPrime + 1; i <= max; i++) {
      if (primeNumbers.values().every((p) => i % p !== 0)) {
        maxPrime = i
        primeNumbers.add(i)
      }
    }
  }

  const primes = primeNumbers.values().toArray()

  return primes.slice(0, primes.findLastIndex((p) => p < max) + 1)
}

function primeFactor(num: number) {
  const result: number[] = [],
    primes = generatePrimes(Math.floor(Math.sqrt(num)))

  while (num !== 1) {
    for (const p of primes) {
      if (num % p === 0) {
        result.push(p)
        num /= p
        break
      }
    }
  }

  return result
}

console.log(primeFactor(180)) // [ 2, 2, 3, 3, 5 ]