题解 | #质数因子#

1. 什么是质数

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

2. 为什么只需要遍历到$\sqrt{n}\backslash sqrt\{n\}$即可

假设我们需要寻找$nn$的质数，当我们找到某个质数$xx$的时候，那么一定存在另一个数$yy$，有$n=x\ast yn\; =\; x\; *\; y$。也就是说，会有一个数$x\le \sqrt{n}x\; \backslash leq\; \backslash sqrt\{n\}$，另一个数$y\ge \sqrt{n}y\; \backslash ge\; \backslash sqrt\{n\}$。如果则乘积，如果$x,y>\sqrt{n}x,y\; >\; \backslash sqrt\{n\}$则有乘积$m>nm\; >\; n$，所以我们只需要遍历到$\sqrt{n}\backslash sqrt\{n\}$即可。

3. JavaScript代码实现

function main() {
    let num = parseInt(readline())
    let res = '', k = Math.sqrt(num)
    for(let i = 2 ; i <= k ; i++) {
        while(num % i === 0) {
            res += i + ' '
            num = Math.floor(num / i)
        }
    }
    // 如果num最后不是1，则说明此时num也是一个质数，需要添加到最后
    if(num !== 1) {
        res += num
    }
    console.log(res)
}

main()