编程算法 - 能被1至n整除的最小数（js）

题意：求出能整除[1,n]中所有数的最小整数，结果对987654321取模。

思路：求出能整除[1,n]中所有数的最小整数，即求出能整除[1,n]中所有素数的最小整数，步骤如下：
1.首先筛选出[1,n]的所有素数，记为primeList[i]。
2.根据算术基本定理：“任何一个合数都可以分解为几个素数的积”，求出每一个Pn的kn值，如下所示：

• 假设Pn表示第n个素数，那么任意正整数可以通过下面的式子获得：

  
  
• Kn 的取值：要保证最终值可以被所有含Pn约数的数整除（如下面例子，要保证Num既能被2整除，也能被4,8整除），因此公式为：primeList[i]^k<=n。

• 例如：一个整数要能被1-10的所有整数整除，那么就等同于他能被1-10之间的所有素数整除。那么此时：

  
  
  

  3.求出各素数次幂的积，即求出Num。

JS代码如下：

var readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
rl.on('line',function(line){
    let n = parseInt(line.trim());
    let prime=primeNum(n);
    let arr=[];
    let result=1;
    for(let i=0,len=prime.length;i<len;i++) {
        for(let j=1;;j++){
            if(Math.pow(prime[i],j)>n){
                arr.push(Math.pow(prime[i],j-1));
                break;
            }
        }
    }
    for(let k=0;k<arr.length;k++) {
        result=result*arr[k];
        if(result>987654321) {
            result=result%987654321;
        }
    }
    result=result%987654321;
    console.log(result)
})
function primeNum(n) {
    let primeList = [];
    if(n>=2) {
        primeList.push(2);
    }
    for (let i = 3; i <= n; i+=2) {
        if (isPrimeNum(i,primeList)){
            primeList.push(i);
        }
    }
    return primeList;
}
function isPrimeNum(num,primeList) {
    for(let i = 3,j = 1; i <= Math.sqrt(num); i = primeList[j++]){
        if(num % i == 0){
            return false;
        }
    }
    return true;
}