介绍

给定一个数 n，打印出所有小于或等于 n 的素数。

当 n 小于 1000 万左右时，埃拉托斯特尼筛法是寻找所有小于 n 的素数的最有效方法之一（参考埃拉托斯特尼筛法 - Wikiwand (opens new window)）。

埃拉托斯特尼筛法（英语：sieve of Eratosthenes ），简称埃氏筛，也称素数筛。这是一种简单且历史悠久的筛法，用来找出一定范围内所有的质数。所使用的原理是从 2 开始，将每个质数的各个倍数，标记成合数。一个质数的各个倍数，是一个差为此质数本身的等差数列。此为这个筛法和试除法不同的关键之处，后者是以质数来测试每个待测数能否被整除。

原理

给出要筛数值的范围 n，找出$\sqrt{n})$ 以内的素数$p1,p2,\dots ,pk$。先用 2 去筛，即把 2 留下，把 2 的倍数剔除掉；再用下一个质数，也就是 3 筛，把 3 留下，把 3 的倍数剔除掉；接下去用下一个质数 5 筛，把 5 留下，把 5 的倍数剔除掉；不断重复下去......。

实现

JavaScript

/**
 * @function SieveOfEratosthenes
 * @description Calculates prime numbers（素数） till input number n
 * @param {Number} n - The input integer
 * @return {Number[]} List of Primes till n.
 * @see [Sieve_of_Eratosthenes](https://www.geeksforgeeks.org/sieve-of-eratosthenes/)
 */
function sieveOfEratosthenes (n) {
  if (n <= 1) return []
  const primes = new Array(n + 1).fill(true) // set all as true initially
  primes[0] = primes[1] = false // Handling case for 0 and 1
  for (let i = 2; i * i <= n; i++) {
    if (primes[i]) {
      for (let j = i * i; j <= n; j += i) primes[j] = false
    }
  }

  return primes.reduce((result, isPrime, index) => {
    if (isPrime) result.push(index)
    return result
  }, [])
}

参考

• Sieve of Eratosthenes - Wikiwand (opens new window)
• 埃拉托斯特尼筛法 - Wikiwand (opens new window)