js 筛选质数

发表于 | 阅读次数:

质数的问题

最近在看基础知识点，遇到一个小练习，使用 filter来完成1-100 里质数的筛选。

那什么是质数呢？

经过百度后：

质数（prime number）又称素数，有无限个。
质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。

这里就可以排除掉 1了。

现在还剩下 2-100这99个数。

比较传统的方法就是让每个数字从1开始除到它本身，若中间没有可以整除的则是质数，否则是合数。但是这个做的话会很耗时间。因为如果是素数的话循环要从2-它本身，数字小当然看不出来，若是十几万的数呢，性能方面很耗啊。

埃拉托色尼素数筛选法

这里有个很巧妙的的素数筛选法，不需要素数循环从2-它本身才判断出来是素数：

埃拉托色尼素数筛选法可以很快速的计算出1到N之间的所有素数。将n开根号，即N^0.5，去掉2到N^0.5中所有素数的倍数，剩下的数便都是素数了。

简单总结一下就是：
只要小于或等于根号N的数（1除外）不能整除N，则N一定是素数；
反过来说就是只要小于或等于根号N的数（1除外）能整除N，则N一定是合数。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//代码复制可用

// 筛选质数（素数）
function get_primes(arr) {
    return arr.filter(n => {
    // 直接筛选出2，3
    if (n <= 3) {
        return n > 1;
    }
    // 排除掉偶数和能被3整除的
    if (n % 2 == 0 || n % 3 == 0) {
        return false;
    }
    // 埃拉托色尼素数筛选法:
    // 只要小于或等于根号N的数（1除外）不能整除N，则N一定是素数；
    // 反过来说就是只要小于或等于根号N的数（1除外）能整除N，则N一定是合数    
    for (let i = 2; i <= Math.sqrt(n); i++) {
        if (n % i === 0) {
        return false
        }
    }
    return true;
    })
}

// 测试:
var
    x,
    r,
    arr = [];
for (x = 1; x < 100; x++) {
    arr.push(x);
}
r = get_primes(arr);

if (r.toString() === [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89,97].toString()) {
    console.log('测试通过!');
} else {
    console.log('测试失败: ' + r.toString());
}