文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

怎么用javascript正则表达式判断质数

2023-06-30 16:20

关注

这篇文章主要介绍“怎么用javascript正则表达式判断质数”,在日常操作中,相信很多人在怎么用javascript正则表达式判断质数问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”怎么用javascript正则表达式判断质数”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!

示例

perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' [number]

翻译成JS代码如下

function isPrime(n) {    return !/^1?$|^(11+?)\1+$/.test("1".repeat(n))}

代码逻辑非常简单,生成"1" * n长度的字符串,通过/^1?$|^(11+?)\1+$/正则表达式进行判断,再将结果取反

正则分析

/^1?$|^(11+?)\1+$/

上面正则表达式有2个分支,分别是

分支1 逻辑很简单,就是匹配0或者1个 "1",因为要排除数字1(非质数)

分支2 就有意思了,可以拆成2块来看

表达式1,非贪婪模式下匹配 "11" "111" "1111"....,作为一个分组
表达式2,\1代表将表达式1匹配的结果赋值给\1,判断是否结尾,否的话会触发回溯(因为表达式1可能匹配多种情况)

举个例子就更清晰了,比如传入n = 9,分支1不满足可以直接忽略
^(11+?)\1+$

步骤匹配结果说明
step 11 1 1 1 1 1 1 1 1(11+?)匹配到"11"
step 21 1 1 1 1 1 1 1 1分组结果赋值给\1,那么正则就变成 "11"+$,继续匹配剩余的字符(7个"1")
step 31 1 1 1 1 1 1 1 1再重复3轮的匹配,发现剩余一个"1",不满足$,进行回溯
step 41 1 1 1 1 1 1 1 1还是不满足$,继续回溯
step 51 1 1 1 1 1 1 1 1一直回溯到step 1(11+?)匹配到"111"
step 61 1 1 1 1 1 1 1 1分组结果赋值给\1,那么正则就变成 "111"+$,继续匹配剩余的字符(6个"1")
step 71 1 1 1 1 1 1 1 1再重复2轮的匹配,满足$,匹配成功

原理

经过上述的分析,不难发现,其实回溯就是将数字不断除于2、3、4....,最后检查是否有余数,没有的话就匹配成功(非质数),非常简单粗暴的穷举法

优化空间

仔细看正则匹配的过程分析,其实step 3 ~ step 4的回溯完全没有必要,那么正则可以改写成这样/^1?$|^(11+?)\1+?$/,将\1+改成非贪婪模式\1+?,那么就放弃step 4回溯

性能测试

console.time('优化前')console.log(!/^1?$|^(11+?)\1+$/.test("1".repeat(33331)));console.timeEnd('优化前')console.time('优化后')console.log(!/^1?$|^(11+?)\1+?$/.test("1".repeat(33331)));console.timeEnd('优化后')// true// 优化前: 227.9189453125 ms// true// 优化后: 155.797119140625 ms

耗时上减少了接近一半

到此,关于“怎么用javascript正则表达式判断质数”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注编程网网站,小编会继续努力为大家带来更多实用的文章!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯