埃拉托斯特尼筛法（埃式筛，筛选数字n范围内的素数）

标签：斯特尼 埃式 自然数 素数 isPrime 埃拉托

 

古希腊数学家 埃拉托色尼/埃拉托斯特尼（Eratosthenes）除了在2000多年前就发现地球不是平的之外，还发明了本文中讨论的埃式筛（一种通过筛除一个素数所有的倍数，从而识别素数方法）。

 

什么是素数：

素数一般指质数。质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

（自然数：全体非负整数组成的集合）

算法思想：

要得到自然数n以内的全部素数，必须把小于或等于的所有素数的倍数剔除，剩下的就是素数。

 

埃式筛代码（筛选特定范围内的素数）

function filter(N) {
    const isPrime = new Array(N).fill(true);
    for (let i = 2; i < N; i++) {
        if (isPrime[i] === false) {
            continue;
        }
        for (let j = i * 2; j < N; j += i) {
            isPrime[j] = false;
        }
    }
    const primes = [];
    for (let i = 2; i < N; i++) {
        if (isPrime[i] === true) {
            primes.push(i); 
        }
    }
    return primes;
}

 

标签：斯特尼,埃式,自然数,素数,isPrime,埃拉托
From： https://www.cnblogs.com/fanqshun/p/16721099.html