这几天遇到几个低级算法题，就想试试写一个判断一个数是不是质数的。

质数是什么？

又称素数，大于1并且只能被自身和1整除的自然数。

思路

其实很简单，做一个循环整除就行了。

先来看看百度到的方法：https://blog.csdn.net/qq_40190624/article/details/108421691

function isPrime(n: number) {
    //  为2是因为质数为2,而且质数不能为1和自身不能被其他自然数整除的数叫做质数;
    for (let i = 2; i < n; i++) {
        if (n % i === 0) {
            return false //质数
        }
    }
    return true //非质数
}

这个经过验证，确实可以简单判断是否为质数，不过小于等于1的数并没有做检测，这个先不管。

然后我就在想，既然是质数，那首先就应该排除偶数（偶数能被2整除），然后被除数也不会超过数的一半（最大无外乎 2x），所以得到了下面这串代码：

function isPrimeNum(num: number) {
    // 小于等于1为非质数
    if (num <= 1) return false;
    // 2能被2整除，所以先特殊处理，直接返回 true
    if (num === 2) return true;
    // 先把小数排除掉
    if (num % 1 !== 0) return false;
    // 排除偶数
    if (num % 2 === 0) return false;
    // 因为 num 最大也只能是 2 倍 x，所以 / 2 向下取整就行
    let halfNum = Math.floor(num / 2);
    // 直接从3开始算
    for (let i = 3; i <= halfNum; i++) {
        if (num % i === 0) return false; // 能被整除，非质数
    }
    return true; // 质数
}

我们和之前那个方法做一个性能测试，列出 1000000 以内的所有质数（打印内容过多，就不做截图了，直接给结果）。第一种方法耗时 98383 毫秒，修改之后耗时 49932 毫秒，可以看到 几乎少了一半的时间。

然后和同事讨论了一下，又有了一个新方案：最大数不是一半，而是开次方根之后的数。修改修改，就变成了以下样子：

function isPrime(num: number) {
    // 小于等于1为非质数
    if (num <= 1) return false;
    // 2能被2整除，所以先特殊处理，直接返回 true
    if (num === 2) return true;
    // 先把小数排除掉
    if (num % 1 !== 0) return false;
    // 排除偶数
    if (num % 2 === 0) return false;
    // 开根号
    let halfNum = Math.sqrt(num);
    // 开根号之后如果直接是整数，那证明不是质数，直接返回
    if (halfNum % 1 === 0) return false;
    // 依然向下取整
    halfNum = Math.floor(halfNum);
    // 直接从3开始算
    for (let i = 3; i <= halfNum; i++) {
        if (num % i === 0) return false; // 能被整除，非质数
    }
    return true; // 质数
}

经过测试，结果依然是对的。好的，我们再来做一次性能测试。这次的耗时仅用时 187 毫秒，几乎只是第一次的 1/490，第二次的 1/250。

等等，既然不能是偶数，那么也不需要每个数都去算了。改一改就变成了：

function isPrime(num: number) {
    // 小于等于1为非质数
    if (num <= 1) return false;
    // 2能被2整除，所以先特殊处理，直接返回 true
    if (num === 2) return true;
    // 先把小数排除掉
    if (num % 1 !== 0) return false;
    // 排除偶数
    if (num % 2 === 0) return false;
    // 开根号
    let halfNum = Math.sqrt(num);
    // 开根号之后如果直接是整数，那证明不是质数，直接返回
    if (halfNum % 1 === 0) return false;
    // 依然向下取整
    halfNum = Math.floor(halfNum);
    // 直接从3开始算，过滤掉偶数，所以直接+2，能被偶数整除也能被2整除
    for (let i = 3; i <= halfNum; i = i+2) {
        if (num % i === 0) return false; // 能被整除，非质数
    }
    return true; // 质数
}

测试结果一致，看看性能，97毫秒 ！！！仅仅是之前最快速的 一半！！！

到这里基本上就告一段落了，应该会有更高效快速的方法，只是还没想到。