javascript怎么求素数

老静君_2923

老静君_2923

2022-09-20

5418人浏览

原创

求素数的方法: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

3.png

我们看上面图解,可以发现,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 大师之旅:从入门到精通的终极指南

相关文章

java速学教程(入门到精通)
java速学教程(入门到精通)

java怎么学习?java怎么入门?java在哪学?java怎么学才快?不用担心,这里为大家提供了java速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

javascript

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

2023.08.14

7396

4

GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

2026.11.17

20

15

GoFrame框架安装与gf命令行工具
GoFrame框架安装与gf命令行工具

本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.17

40

15

GoFrame框架零基础入门
GoFrame框架零基础入门

本专题整理GoFrame框架的入门知识,从模块化设计理念、环境准备到跑通第一个Web服务,讲清目录分层、配置加载、日志与中间件的用法,并对比Gin、Go-Zero的差异,帮助Go开发者建立整体认知。

2026.11.17

20

15

SQLAlchemy 一对多关系怎么建立
SQLAlchemy 一对多关系怎么建立

SQLAlchemy 一对多关系怎么建立?本专题整理父子表外键、relationship 双向映射、关联查询、级联删除和加载优化等相关文章,帮助你理解并实现常见的 ORM 关系建模。

2026.11.17

20

10

SQLAlchemy 如何增删改查
SQLAlchemy 如何增删改查

SQLAlchemy 如何增删改查?本专题整理 ORM 新增记录、条件查询、更新和删除、Session 事务提交与批量处理等实用文章,帮助你掌握 Python 数据库操作流程。

2026.11.17

40

11

SQLAlchemy ORM 模型怎么写
SQLAlchemy ORM 模型怎么写

SQLAlchemy ORM 模型怎么写?本专题整理模型类定义、Mapped 字段映射、主键与约束、表结构创建和常见报错的相关文章,帮助你从基础配置到实际建模逐步掌握 SQLAlchemy。

2026.11.17

20

16

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

180

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

140

15

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
WebStorm 官方调试文档
WebStorm 官方调试文档

共0课时 | 0人学习

React 教程
React 教程

共58课时 | 12.6万人学习

TypeScript 教程
TypeScript 教程

共19课时 | 6.9万人学习