每日一算法：素数

质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。

埃拉托斯特尼筛法，简称埃氏筛，也称素数筛。是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

JavaScript 实现

使用埃拉托斯特尼筛法（Eratosthenes）产生最多给定数的质数。

• 从 2 到给定数字生成一个数组。

• 使用 Array.prototype.filter() 筛选出可被从 2 到所提供数字的平方根的任何数字整除的值。

const primes = num => {
  let arr = Array.from({ length: num - 1 }).map((x, i) => i + 2) // [2, 3, 4, 5, 6, 7, 8, 9, 10]
  let sqroot = Math.floor(Math.sqrt(num)) // 3
  let numsTillSqroot = Array.from({ length: sqroot - 1 }).map((x, i) => i + 2) // [2, 3]
  numsTillSqroot.forEach(x => (arr = arr.filter(y => y % x !== 0 || y === x)))
  return arr
}

primes(10) // [2, 3, 5, 7]

此示例来自 30 seconds of code 的 primes

Leetcode 相关的素数题目

• 回文素数
• 第 K 个最小的素数分数