在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]