牛客网 – 质数因子

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;
}