数学中素数又称质数，指整数在一个大于1的自然数中，除了1和该整数自身外，无法被其他自然数整除的数。换句话说，素数只有两个正因数：1和它自己。
如何判断一个整数是否为素数呢？根据上面的定义，我们一般会想到用试除法，即遍历从2到该整数的所有整数，挨个拭除，如果因数个数小于2，则为素数，代码如下：
// 简单粗暴的试除法
function isPrime(num) {
if (num <= 1) return false;
var result = [];
for (var i = 2; i <= num; i++) {
if (num % i === 0) {
result.push(i);
}
}
return result.length < 2;
}上面的算法比较简单粗暴，但是效率是最差的，时间复杂度 O(n) 。仔细观察会发现：一个数如果有（自身除外）质因数，其质因素肯定小于等于这个数的一半，所以我们不必一直遍历完所有数字，只需要循环到这个数的一半就可以了，优化后的代码如下：
// 拭除法进阶
function isPrime(num) {
for (var i = 2; i < num / 2; i++) {
if (num % i === 0) return false; // 如果有因数，可以直接断定为非素数
}
return num < 2 ? false : true;
}上面的算法将时间复杂度减少了一半，为 O(n/2)。因为一个整数的因数都是成对出现的，例如8的因数有：1和8，2和4，4和2，这些成对因数中，一个必然小于 √n，另一个必然大于 √n，所以可以继续优化代码如下：
// 平方根法
function isPrime(num) {
for (var i = 2; i < Math.sqrt(num); i++) {
if (num % i === 0) return false;
}
return num < 2 ? false : true;
}上面的算法，时间复杂度为 O(√n)（？）。
还有一种更好的算法，我不是很懂，小伙伴们自行感受：
// 筛选法
function isPrime(num) {
if (num <= 1) return false;
if (!!~[3, 5, 7, 11].indexOf(num)) return true;
if (num % 2 === 0 || num % 3 === 0) return false;
for (var i = 5; i <= Math.pow(num, 0.5); i += 6) {
if (num % i === 0 || num % (i + 2) === 0) {
return false;
}
}
return true;
}
本文参考自：https://www.cnblogs.com/caiminfeng/p/4805544.html
Visitar URL original
数学中素数又称质数，指整数在一个大于1的自然数中，除了1和该整数自身外，无法被其他自然数整除的数。换句话说，素数只有两个正因数：1和它自己。
如何判断一个整数是否为素数呢？根据上面的定义，我们一般会想到用试除法，即遍历从2到该整数的所有整数，挨个拭除，如果因数个数小于2，则为素数，代码如下：
上面的算法比较简单粗暴，但是效率是最差的，时间复杂度 O(n) 。仔细观察会发现：一个数如果有（自身除外）质因数，其质因素肯定小于等于这个数的一半，所以我们不必一直遍历完所有数字，只需要循环到这个数的一半就可以了，优化后的代码如下：
上面的算法将时间复杂度减少了一半，为 O(n/2)。因为一个整数的因数都是成对出现的，例如8的因数有：1和8，2和4，4和2，这些成对因数中，一个必然小于 √n，另一个必然大于 √n，所以可以继续优化代码如下：
上面的算法，时间复杂度为 O(√n)（？）。
还有一种更好的算法，我不是很懂，小伙伴们自行感受：