牛客网 – 质数因子

https://www.nowcoder.com/share/jump/55776421719918468907

描述

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

数据范围：1≤n≤2×109+14 

输入描述：

输入一个整数

输出描述：

按照从小到大的顺序输出它的所有质数的因子，以空格隔开。

示例1

输入：

180

复制

输出：

2 2 3 3 5

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

void async function () {
    while (line = await readline()) {
        let num = parseInt(line.trim());
        let factors = getPrimeFactors(num);
        console.log(factors.join(' '));
    }
}()

function getPrimeFactors(n) {
    let factors = [];
    
    // 处理2的因子
    while (n % 2 === 0) {
        factors.push(2);
        n = Math.floor(n / 2);
    }
    
    // 从3开始处理其他质因子
    let factor = 3;
    while (factor * factor <= n) {
        while (n % factor === 0) {
            factors.push(factor);
            n = Math.floor(n / factor);
        }
        factor += 2;
    }
    
    // 如果 n 本身是一个大于2的质数
    if (n > 2) {
        factors.push(n);
    }
    
    return factors;
}