求素数的方法:1、遍历1~n区间中的所有自然数给n来除,若余数为0则表示该数n不是素数,否则就是素数,语法“for(i=2;i

本教程操作环境: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个。
JavaScript判定素数的四种方法
1、素数只能被1和自身整除
素数只能被1和自身整除,所以遍历(1,n)开区间中的所有自然数给n来除,若存在整除,即余数为0,则表示该数n不是素数,否则就是素数。
function isPrime(n) {
n = parseInt(n);
if (n 1;
}
for (let i = 2; i <p>但是这种算法的复杂度为O(n)</p><h3 id="%E7%B4%A0%E6%95%B0%E5%B9%B3%E6%96%B9%E6%A0%B9%E8%8C%83%E5%9B%B4"><strong>2、素数平方根范围</strong></h3><p>假设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)中。</p><pre class="brush:php;toolbar:false;">function isPrime(n) {
n = parseInt(n);
if (n 1;
}
for (let i = 2; i <p>此时算法复杂度为O(sqrt(n))</p><h3 id="%E7%B4%A0%E6%95%B0%E4%B8%8D%E8%83%BD%E6%98%AF%E9%99%A4%E4%BA%862%E5%A4%96%E7%9A%84%E5%81%B6%E6%95%B0"><strong>3、素数不能非2的其他偶数</strong></h3><p>除了2,所有偶数都不是素数</p><p><img src="https://img.php.cn/upload/image/644/149/762/1663645614907138.png?x-oss-process=image/resize,p_40" title="1663645614907138.png" alt="1.png"></p><pre class="brush:php;toolbar:false;">function isPrime(n) {
n = parseInt(n);
if (n 1;
}
if (n % 2 === 0) {
return false;
}
for (let i = 3; i <p>for循环中n,只能为上图浅蓝色部分。</p><p>因此上面算法减少了一半的循环,时间复杂度为O(sqrt(n) / 2) </p><p>需要注意的是,本算法的代码不能将n % 2 === 0 的判断条件加入到循环中,如下代码存在漏洞</p><pre class="brush:php;toolbar:false;">function isPrime(n) {
n = parseInt(n);
if (n 1;
}
for (let i = 3; i <p>此时4、6、8都会被判定为素数。</p><p>漏洞形成的原因是,for循环的循环条件 i </p><p>该算法只能保证循环条件 i = i^2 = 9 时。</p><h3 id="%E5%A4%A7%E4%BA%8E%E7%AD%89%E4%BA%8E5%E7%9A%84%E7%B4%A0%E6%95%B0%E4%B8%80%E5%AE%9A%E5%92%8C6%E7%9A%84%E5%80%8D%E6%95%B0%E7%9B%B8%E9%82%BB"><strong>4、大于等于5的素数一定和6的倍数相邻</strong></h3><p>大于等于5的素数一定和6的倍数相邻</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill12835" title="JavaScript 测试模式"><img
src="https://img.php.cn/upload/skill/001/246/273/6adaf20cf0281539.jpg" alt="JavaScript 测试模式" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/skill12835" title="JavaScript 测试模式" class="overflowclass">JavaScript 测试模式</a>
<p class="overflowclass">使用 Jest、Vitest 和 Testing Library 实施全面的测试策略,包括单元测试、集成测试和端到端测试,涵盖模拟、测试夹具和测试驱动开发。在编</p>
</div>
<a rel="nofollow" href="/xiazai/skill12835" title="JavaScript 测试模式" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div><p>(注意这句话不等价于:<span style="text-decoration:line-through;">和6的倍数相邻的数一定是大于5的素数</span>,该结论不成立。)</p><p><img src="https://img.php.cn/upload/image/346/360/896/1663645626679081.png?x-oss-process=image/resize,p_40" title="1663645626679081.png" alt="2.png"></p><p>如上图中,将大于等于5的数分为了:6y-1、6y、6y+1、6y+2、6y+3、6y+4(y>=1)</p><p>其中,6y、6y+2、6y+3、6y+4都不可能是素数,只有6y-1和6y+1<strong><span style="max-width:90%">可能</span></strong>是素数。</p><p>另外,6y-1(y>=1)和 6y + 5 (y>=0)等价。</p><p>所以,我们可以将n不为6y-1(或6y+5)和6y+1的数直接排除,排除方法为,</p><pre class="brush:js;toolbar:false"> if (n % 6 !== 1 && n % 6 !== 5) {
return false;
}
下面要剔除掉6y-1(或6y+5)和6y+1中的非素数,
for (let i = 5; i <p>这里大家比较疑惑的可能有两点:</p>
- 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 1;
}
if (n % 6 !== 1 && n % 6 !== 5) {
return false;
}
for (let i = 5; i <p>此时时间复杂度为 O(sqrt(n) / 3) <br></p><p>【相关推荐:<a href="https://www.php.cn/course/list/17.html" target="_blank" textvalue="javascript视频教程">javascript视频教程</a>、<a href="https://www.php.cn/course/list/91.html" target="_blank" textvalue="编程基础视频">编程基础视频</a>】</p>
Java免费学习笔记:立即使用
解锁 Java 大师之旅:从入门到精通的终极指南










