[教程]js判断质数(素数)的多种方式

质数（prime number）又称素数，有无限个。 质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数 ，  了解了这个 很容易就能写出判断条件。普通写法最简单的方法就是遍历小于目标数字...

质数（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等方法。