您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
这篇文章主要讲解了“javascript如何求素数”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“javascript如何求素数”吧！
求素数的方法：1、遍历1~n区间中的所有自然数给n来除，若余数为0则表示该数n不是素数，否则就是素数，语法“for(i=2;i<n;i++){if(n%i===0){return false;}}”。2、利用素数平方根范围，语法“for(i=2;i<=Math.sqrt(n);i++){if(n%i===0){return false;}}”。
本教程操作环境：windows7系统、javascript1.8.5版、Dell G3电脑。
素数又叫质数，素数是指在大于1的自然数中，除了1和它本身以外，不能被其他自然数整除的数。
100以内的素数：2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97，共计25个。
素数只能被1和自身整除，所以遍历（1，n）开区间中的所有自然数给n来除，若存在整除，即余数为0，则表示该数n不是素数，否则就是素数。
function isPrime(n) {
n = parseInt(n);
if (n <= 3) {
return n > 1;
}
for (let i = 2; i < n; i++) {
if (n % i === 0) {
return false;
}
}
return true;
}但是这种算法的复杂度为O(n)
假设n不是素数，则n除了可以被1和n整除外，还可以被i、j整除，即 n / i = j...0，比如15不是素数，15 / 3 = 5，比如35不是素数，35 / 5 = 7，此时i,j必然分别处于(1, Math.sqrt(n)]和[Math.sqrt(n), n） 之中，比如Math.sqrt(15) ≈ 3.8，则 3处于（1，3.8]，5处于[3.8, 15）。比如Math.sqrt(4) = 2，则2处于(1,2]中，也处于[2,4)中。
function isPrime(n) {
n = parseInt(n);
if (n <= 3) {
return n > 1;
}
for (let i = 2; i <= Math.sqrt(n); i++) {
if (n % i === 0) {
return false;
}
}
return true;
}此时算法复杂度为O（sqrt(n)）
除了2，所有偶数都不是素数
function isPrime(n) {
n = parseInt(n);
if (n <= 3) {
return n > 1;
}
if (n % 2 === 0) {
return false;
}
for (let i = 3; i <= Math.sqrt(n); i += 2) {
if (n % i === 0) {
return false;
}
}
return true;
}for循环中n，只能为上图浅蓝色部分。
因此上面算法减少了一半的循环，时间复杂度为O（sqrt(n) / 2）
需要注意的是，本算法的代码不能将n % 2 === 0 的判断条件加入到循环中，如下代码存在漏洞
function isPrime(n) {
n = parseInt(n);
if (n <= 3) {
return n > 1;
}
for (let i = 3; i <= Math.sqrt(n); i += 2) {
if (n % 2 === 0 || n % i === 0) {
return false;
}
}
return true;
}此时4、6、8都会被判定为素数。
漏洞形成的原因是，for循环的循环条件 i <= Math.sqrt(n) 不成立，比如n=4时，i <= Math.sqrt(4) 不成立，导致n无法进入循环中n % 2 === 0 的判断，而是直接退出循环，return true。
该算法只能保证循环条件 i <= Math.sqrt(n) 成立的n值判断素数正确，即 n >= i^2 = 9 时。
大于等于5的素数一定和6的倍数相邻
（注意这句话不等价于：和6的倍数相邻的数一定是大于5的素数，该结论不成立。）
如上图中，将大于等于5的数分为了：6y-1、6y、6y+1、6y+2、6y+3、6y+4（y>=1）
其中，6y、6y+2、6y+3、6y+4都不可能是素数，只有6y-1和6y+1可能是素数。
另外，6y-1（y>=1）和 6y + 5 （y>=0）等价。
所以，我们可以将n不为6y-1（或6y+5）和6y+1的数直接排除，排除方法为，
if (n % 6 !== 1 && n % 6 !== 5) {
return false;
}下面要剔除掉6y-1（或6y+5）和6y+1中的非素数，
for (let i = 5; i <= Math.sqrt(n); i += 6) {
if (n % i === 0 || n % (i + 2) === 0) {
return false;
}
}这里大家比较疑惑的可能有两点：
for循环i自增为啥是 6
for循环中素数判定的条件为啥是 n % i === 0 || n % (i+2) === 0
我们看上面图解，可以发现，6y-1，是基数为5，差值为6的等差数列，即 5 + 6x :
对于 5 + 6x 而言，如果x为5的倍数（5 * z），则5 + 6x = 5 + 6 * 5 * z = 5 *（1+6z）,则此时5 + 6x可以被5整除。
5 + 6x 还可以转化为 5 + 6 + 6 * (x-1) = 11 + 6(x-1)，则只要x-1为11的倍数，则5 + 6x可以被11整除，
5 + 6x 还可以转化为 5 + 12 + 6 * (x-2) = 17 + 6(x-2)，则只要x-2为17的倍数，则5 + 6x可以被17整除
......
6y+1，是基数为7，差值为6的等差数列，即 7 + 6x :
对于 7 + 6x 而言，如果x为7的倍数（7 * z），则7 + 6x = 7 + 6 * 7 * z = 7 *（1+6z）,则此时7 + 6x可以被7整除。
7 + 6x 还可以转化为 7 + 6 + 6 * (x-1) = 13 + 6(x-1)，则只要x-1为13的倍数，则7 + 6x可以被13整除，
7 + 6x 还可以转化为 7 + 12 + 6 * (x-2) = 19 + 6(x-2)，则只要x-2为19的倍数，则7 + 6x可以被19整除，
......
所以6y-1和6y+1可能整除的数自增量为6，这是for循环i自增为啥是 6的原因
且6y-1和6y+1的整除数基数为5和7，相差为2，这是for循环中素数判定的条件为啥是 n % i === 0 || n % (i+2) === 0的原因
function isPrime(n) {
n = parseInt(n);
if (n <= 3) {
return n > 1;
}
if (n % 6 !== 1 && n % 6 !== 5) {
return false;
}
for (let i = 5; i <= Math.sqrt(n); i += 6) {
if (n % i === 0 || n % (i + 2) === 0) {
return false;
}
}
return true;
}此时时间复杂度为 O（sqrt(n) / 3）
感谢各位的阅读，以上就是“javascript如何求素数”的内容了，经过本文的学习后，相信大家对javascript如何求素数这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。