关于快速获取N个质数算法

背景来源于很久前组内的一次讨论，如何可以更高效的获取N个质数。
使用场景是很久前在对选择商品多属性SKU的情况下，选中某些属性的情况下，判断其它属性的选中状态，通过质数的方式来做可选操作判断。
关于质数方案原文应该是出在淘宝某团队，这里只讨论关于获取质数的一些方法

纯粹循环

这种方法是最容易理解和想到的方法，依次从2到当前数字，如果任意一个能被整除那就不是质数
首先来提供一个测试方法，通过传入一个方法验证10万内的所有质数，代码如下：

/* GLOBAL js */
window.getPrimeNumArr = (fn, n = 10 * 10000) => {
    console.time(fn.fnName);
    const primeNumList = [2];
    for (let i = 3; i < n; i++) {
        if (fn(i, primeNumList)) {
            primeNumList.push(i)
        }
    }
    console.timeEnd(fn.fnName);
    console.log(primeNumList);
    console.log(`${n}共有：${primeNumList.length}个`);
    console.log('--------------------');
    return primeNumList;
}

纯粹循环判断是否为质数的方法：

function isPrimeNum(num) {
    for (let i = 2; i < num; i++) {
        if (num % i === 0) {
            return false;
        }
    }
    return true;
}
isPrimeNum.fnName = '纯粹循环';
getPrimeNumArr(isPrimeNum)

点击上面代码块 运行单个 按钮，纯粹循环大概要消耗2s的时间。

整除质数

只用需要判断的数字去除以已有的质数，计算是否可整除，都不能被整除的就为质数。

function isPrimeNum2(num, list) {
    for (let i = 0; i < list.length; i++) {
        if (num % list[i] === 0) {
            return false
        }
    }
    return true
}
isPrimeNum2.fnName = '整除质数';
window.getPrimeNumArr(isPrimeNum2);

点击运行全部，可以看到对比第一种方法速度已经提升了大概10倍，当然还可以更快看下面的方法

开平方

需要判断的数字进行一次开平方计算，然后判断开平方后的数字是不是可以被小于他的数字整除

// 开平方
function isPrimeNum3(num) {
    const sqrt = Math.floor(Math.sqrt(num))
    for (let i = 2; i <= sqrt; i++) {
        if (num % i === 0) {
            return false;
        }
    }
    return true;
}
isPrimeNum3.fnName = '开平方';
window.getPrimeNumArr(isPrimeNum3);

点击运行全部，对比第一种方法已经提升了100多倍的速度

结合开平方和整除质数

上述两种方法的结合版

// 开平方加已存在的质数
function isPrimeNum4(num, list) {
    const sqrt = Math.floor(Math.sqrt(num))
    for (let i = 0; i < list.length; i++) {
        if (list[i] > sqrt) {
            return true;
        }
        if (num % list[i] === 0) {
            return false;
        }
    }
    return true;
}
isPrimeNum4.fnName = '开平方+整除质数';
window.getPrimeNumArr(isPrimeNum4);

速度对比前一种方法，又有了1倍的提升。

小结

从最原始的方法都后面优化过得算法性能提升了大概200多倍，至于每种算法原理和复杂度分析等下次再来补上吧。
虽然在日常开发中我们很难遇到这种需要大量计算的场景，但关注更优的实现对自己的要求高一点总是好事。