求素数的方法:1、遍历1~n区间中的所有自然数给n来除,若余数为0则表示该数n不是素数,否则就是素数,语法“for(i=2;i5af19ed287589000ea46aa3b5ec732c1 1; } for (let i = 2; i 473403c6b9575c622b9ebe6067a56cab 1; } for (let i = 2; i 5d84a44e85fad21b64a1a98595da400c 1; } if (n % 2 === 0) { return false; } for (let i = 3; i e4ebc73d51900390b2034910a358a72c 1; } for (let i = 3; i 2fa1a152003a477da9b77bb1ab80f363= i^2 = 9 时。
4、大于等于5的素数一定和6的倍数相邻
大于等于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 03a568b98383134c20bbb7dc9f7d8b51 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怎么求素数的详细内容。更多信息请关注PHP中文网其他相关文章!