前言

在做 codewars 一个题目时，涉及到素数的计算，便想写个函数，查找传入值范围内所有的素数。在这个过程中，了解到一个方法，因此做此记录，并打算记录类似工具类函数集。

埃拉托斯特尼筛法

这是个关于素数的快速筛选，详情见 埃拉托斯特尼筛法-百度百科 或 埃拉托斯特尼筛法-维基百科-推荐

思路

根据埃拉托斯特尼筛法，从 2 开始的数组，将 2 的倍数过滤后，数组的第一个元素也是素数。然后循环将此元素的倍数过滤，剩下来的数组第一个元素也是素数。依次循环…

实现

function primesFn(N) {
    if (N < 2) return [];
    let primes = []; // 素数 数组
    let nums = []; // 数据源
    for (let i = 2; i < N + 1; i++) {
        nums.push(i);
    }

    // 循环过滤数组。 使用filter筛选
    while (nums.length) {
        let p = nums.shift();
        primes.push(p);

        nums = nums.filter((a) => a % p !== 0);
    }
    return primes;
}

结语

面对有规律的题目，要舍弃暴力 for 循环计算，转而思考怎么使用规律，简化算法。

对于这个题目，也可通用。两层 for 循环也能找出给定范围内的素数，但效率会随着范围越大越低。

另外，在实现中，没有使用递归调用，而是用了 while 条件，是因为已经知道当 nums 数据源为空的时候，就是找到了所有的素数。将比递归更易懂。