题解 | 质数因子

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 = parseInt(await readline());
    // 结果质因子数组。
    const result = [];
    // 暴力遍历。注意，X的质因子一定小于等于根号X，即质因子的范围为2到√X。
    for (let index = 2; index * index <= num; index++) {
        // 如果能整除，说明num有一个因子为index。
        while (num % index === 0) {
            // 把当前因子--index放入结果数组中。
            result.push(index);
            num = num / index;
        }
    }
    // 最后必定有一个因子整除不了。
    if (num > 1){
        result.push(num);
    }
    console.log(...result);
})();

核心重点在X的质因子一定小于等于根号X，即质因子的范围为2到√X。如果不能理解这点，时间基本上一定会超出。

以上是暴力破解法。就是直接 整除，如果无余数，则说明能被整除。

整除一定要整除彻底，所以while(num % index === 0){}就是防止2*2*2这类的情况。

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

void (async function () {
    // Write your code here
    // 获取质数列表。
    const pList = [];
    for (let theNum = 2; theNum * theNum <= 2 * 10 ** 9 + 14; theNum++) {
        let isP = true;
        for (let index = 0; index < pList.length; index++) {
            if (theNum % pList[index] === 0) {
                isP = false;
                break;
            }
        }
        if (isP) {
            pList.push(theNum);
        }
    }
    while ((line = await readline())) {
        let isNext = true;
        let nowNum = Number(line);
        const theList = [];
        while (isNext) {
            // 如果在质数表中，则直接返回。
            if (pList.includes(nowNum)) {
                theList.push(nowNum);
                isNext = false;
                break;
            }
            // 判断是否整除过质数了。
            let isHas = false;
            // 根据质数表来分解出质数。
            for (let index = 0; index < pList.length; index++) {
                if (nowNum % pList[index] === 0) {
                    theList.push(pList[index]);
                    nowNum = nowNum / pList[index];
                    // 至少分解出一个质数了，就退出for循环。同时记录下来。
                    isHas = true;
                    break;
                }
            }
            // 如果没分解过一个质数，同时也不在质数表中，则说明最后一个数是大于质数表的一个质数。
            if (!isHas && !pList.includes(nowNum)) {
                theList.push(nowNum);
                isNext = false;
            }
        }
        console.log(...theList);
    }
})();