Skip to content

在JavaScript中检查一个数是否为质数

在数学和计算机科学中,检查质数是一项常见任务。在编码面试和挑战中也很常见。让我们看看如何检查一个数是否为质数,以及如何生成小于给定数的质数。

检查一个数是否为质数

要检查一个整数是否为质数,我们可以简单地使用一个for循环。在循环内部,我们可以检查该数是否能被从2到给定数的平方根之间的任何数整除。如果找到这样的数,我们可以返回false。如果找不到这样的数,则可以返回true,除非该数小于2

const isPrime = num => {
  const boundary = Math.floor(Math.sqrt(num));
  for (let i = 2; i <= boundary; i++) if (num % i === 0) return false;
  return num >= 2;
};

isPrime(11); // true

[!NOTE]

对于非常大的数,这段代码可能相当低效。可以进行优化,但超出了本文的范围。

生成小于给定数的质数

使用埃拉托斯特尼筛法算法,我们可以生成小于给定数的质数。该算法的工作原理如下:

  • 2到给定数生成一个数组。
  • 使用Array.prototype.filter()来过滤掉能被从2到提供的数的平方根之间的任何数整除的值。
const primes = num => {
  let arr = Array.from({ length: num - 1 }).map((x, i) => i + 2),
    sqroot = Math.floor(Math.sqrt(num)),
    numsTillSqroot = Array.from({ length: sqroot - 1 }).map((x, i) => i + 2);
  numsTillSqroot.forEach(x => (arr = arr.filter(y => y % x !== 0 || y === x)));
  return arr;
};

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

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