质数(prime number)又称素数,有无限个。 质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数 , 了解了这个 很容易就能写出判断条件。
最简单的方法就是遍历小于目标数字的数,挨个与目标数字相除,代码如下:
//判断是否质数
function isPrime(num) {
if (num <= 1 || !Number.isInteger(num)) {//1不是质数 || 非整数
return false
}
if (num === 2) {
return true
}
for (let i = 2; i < num; i++) {
if (num%i === 0) {
return false
}
}
return true
}
}
使用该方式判断数字很大时会导致计算量变大。所以对于数字很大的推荐使用下一种判断方法。
原理:一个数如果可以进行因数分解,那么必定一个因数<=他的平方根 另一个因数>=他的平方根 那么只需要从2开始 到平方根为止,如果能被整除 就代表不是质数。
那么可以将num%i === 0改为Math.sqrt(num)%i === 0,减少循环的次数。对于1和2的判断,可以合并一下:
function isPrime(num) {
if (!Number.isInteger(num)) {//非整数
return false
}
if (num <= 3) {
return num > 1
}
let temp = Math.sqrt(num) //取平方根
for (let i = 2; i <= temp; i++) { //循环判断
if (num%i === 0) {
return false
}
}
return true
}
使用的是正则的方法,果然是简短,而且代码效率远远高于上面的2种方法。
function isPrime(num){
if (num <=0 || !Number.isInteger(num)) {//非大于0的整数
return false
}
return !/^.?$|^(..+?)\1+$/.test(Array(num + 1).join('1'))
}
这是一道常见面试题,在上面我们知道了如何判断质数,那么筛选数组中的质数就很好写了
const oldArr = [11,23,44,12,13,56,71,97]
const newArr = oldArr.filter(isPrime)
console.log(newArr) // [11, 23, 13, 71, 97]
或者根据需求使用forEach、map等方法。
1 天前