【JavaScript】质数因子分解【逐步除法】🧮

一、算法思路

质数因子分解问题要求我们将一个正整数分解为它的质因子，并按从小到大的顺序输出这些因子。质数因子是指只能被 1 和自身整除的自然数，比如 2、3、5、7、11 等。

我们的思路是通过 逐步除法 来将数字 n 分解为质因子。具体步骤如下：

1. 从 2 开始尝试分解：
   • 我们从最小的质数 2 开始，检查 n 是否能被 2 整除。如果可以，则说明 2 是 n 的一个质因子。
   • 每次发现能整除，就将 n 除以 2，直到不能再被 2 整除为止。
2. 继续检查更大的因子：
   • 继续尝试从 3 开始，检查 n 是否能被 3 整除。如果能，继续除以 3。
   • 这样不断尝试每一个整数，直到 i * i > n（即 i 的平方大于 n）。
3. 处理剩余部分：
   • 如果 n 在经过这些因子分解后仍大于 1，那么 n 本身就是一个质因子。
4. 输出质因子：
   • 最终，将所有质因子按从小到大的顺序输出。

二、代码实现

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    // 读取输入的数字并转换为整数
    let num = Number(await readline());  
    let res = [];  // 用于存储质因子

    // 从 2 开始尝试每一个数字，直到 sqrt(num)
    for (let i = 2; i * i <= num; i++) {
        // 如果 i 能整除 num，说明 i 是一个质因子
        while (num % i === 0) {
            res.push(i);  // 将质因子 i 加入到结果数组
            num /= i;  // 将 num 除以 i，继续分解
        }
    }

    // 如果剩下的 num 大于 1，说明 num 本身是一个质因子
    if (num > 1) {
        res.push(num);  // 将 num 本身添加到质因子数组
    }

    // 输出所有质因子，以空格分隔
    console.log(res.join(' ').trim());
})();

为什么只需要尝试到 sqrt(n)？

因子是成对出现的： 假设 n = a * b，其中 a 和 b 是 n 的因子。那么，如果 a 和 b 都大于 sqrt(n)，则 a * b 必然大于 n。反之，如果 a 和 b 都小于 sqrt(n)，那么 a * b 必然小于 n。

也就是说，n 的因子总是成对出现的。如果有一个因子小于 sqrt(n)，那么另一个因子一定大于 sqrt(n)。

三、复杂度分析

• 时间复杂度： O(√n)
  • 我们只需要检查 2 到 √n 范围内的数字，复杂度为 O(√n)。
  • 在最坏情况下，每个质因子都会被加入到结果数组中，因此时间复杂度是 O(√n)。
• 空间复杂度： O(log n)
  • 质因子的个数最多为 O(log n)，因为每次分解都会将 num 除以一个质因子，最终剩余部分小于等于 num。
  • 所以空间复杂度是 O(log n)，存储所有的质因子。