查找范围内的素数 - 埃拉托斯特尼筛法

2018/11/08 Algorithm 共 605 字,约 2 分钟

前言

在做 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 数据源为空的时候,就是找到了所有的素数。将比递归更易懂。

文档信息

Search

    Table of Contents