一行正则表达式判断质数的代码
更新时间：2022年5月26日 20:09 点击：1218 作者：jayzou
背景
昨天无意中看到一篇大佬的文章Primality regex（正则表达式判断质数），惊为天人，正则表达式也能用来判断质数了？立马来研究下
示例
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?$^(11+?)\1+$
分支1 逻辑很简单，就是匹配0或者1个 "1"，因为要排除数字1（非质数）
分支2 就有意思了，可以拆成2块来看
^(11+?)\1+$
表达式1，非贪婪模式下匹配 "11" "111" "1111"....，作为一个分组
表达式2，\1代表将表达式1匹配的结果赋值给\1，判断是否结尾，否的话会触发回溯（因为表达式1可能匹配多种情况）
举个例子就更清晰了，比如传入n = 9，分支1不满足可以直接忽略^(11+?)\1+$
| 步骤 | 匹配结果 | 说明 |
|---|---|---|
| step 1 | 1 1 1 1 1 1 1 1 1 | (11+?)匹配到"11" |
| step 2 | 1 1 1 1 1 1 1 1 1 | 分组结果赋值给\1，那么正则就变成 "11"+$，继续匹配剩余的字符(7个"1") |
| step 3 | 1 1 1 1 1 1 1 1 1 | 再重复3轮的匹配，发现剩余一个"1"，不满足$，进行回溯 |
| step 4 | 1 1 1 1 1 1 1 1 1 | 还是不满足$，继续回溯 |
| step 5 | 1 1 1 1 1 1 1 1 1 | 一直回溯到step 1，(11+?)匹配到"111" |
| step 6 | 1 1 1 1 1 1 1 1 1 | 分组结果赋值给\1，那么正则就变成 "111"+$，继续匹配剩余的字符(6个"1") |
| step 7 | 1 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
耗时上减少了接近一半
总结
其实这个正则性能非常差（穷举法），实用性不高，但是思路很让人惊艳
到此这篇关于一行正则表达式判断质数的文章就介绍到这了,更多相关正则表达式判断质数内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞！
原文出处：https://juejin.cn/post/7100756012746932255
上一篇: 正则表达式详析+常用示例
下一篇: 正则表达式的基本语法汇总篇(推荐!)
相关文章
- 取双引号内的内容我们如果一个字符串中只有一个可以使用explode来获得，但如果有多个需要使用正则表达式来提取了，具体的例子如下。 写程序的时候总结一点经验，如何只...2016-11-25
- 今天遇到一个正则匹配的问题，忽然翻到有捕获组的概念，手册上也是一略而过，百度时无意翻到C#和Java中有对正则捕获组的特殊用法，搜索关键词有PHP时竟然没有相关内容，自己试了一下，发现在PHP中也是可行的，于是总结一下，分享的同...2015-11-08
- 正则表达式是一门非常有用的并且进行模糊判断的一个功能了，我们下面来看通过正则来验证输入汉字、英语、数字，具体如下。 收藏了正则表达式。可以验证只能输入数...2016-11-25
- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
- 常用的日期时间正则表达式 下面收藏了大量的日期时间正则匹配函数，包括分钟，时间与秒都能达到。 正则表达式 (?n:^(?=d)((?<day>31(?!(.0?[2469]|11))|30(?!.0?2)|29(...2016-11-25
- 网址规则是可寻的，所以我们可以使用正则表达式来提取字符串中的url地址了，下面一起来看看小编整理的几个PHP正则表达式匹配验证提取网址URL实例. 匹配网址 URL 的...2016-11-25
- 这篇文章主要介绍了正则表达式中两个反斜杠的匹配规则,本文给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下...2021-05-07
- 这篇文章主要介绍了C#正则表达式使用方法,大家参考使用...2020-06-25
- 这篇文章给大家详细介绍了JS中使用正则表达式g模式和非g模式的区别，非常不错，具有参考借鉴价值，需要的朋友参考下吧...2017-04-03
- c#正则表达式,用于字符串处理、表单验证等场合，实用高效。现将一些常用的表达式收集于此，以备不时之需。...2020-06-25
- 本文主要介绍了JavaScript利用正则表达式替换字符串中内容的具体实现方法，并做了简要注释，便于理解。具有一定的参考价值，需要的朋友可以看下...2017-01-09
- 这篇文章主要介绍了python正则表达式常用函数及使用方法，本文给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-05-07
- 这篇文章给大家介绍了Idea使用正则表达式批量替换字符串的方法，本文给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友参考下吧...2021-07-21
- 今天遇到一个正则匹配的问题，忽然翻到有捕获组的概念，手册上也是一略而过，百度时无意翻到C#和Java中有对正则捕获组的特殊用法，搜索关键词有PHP时竟然没有相关内容，自己试了一下，发现在PHP中也是可行的，于是总结一下，分享的同...2015-11-08
- 正则表达式的作用用来描述字符串的特征。本文重点给大家介绍C# 中使用正则表达式匹配字符的含义，非常不错，具有一定的参考借鉴价值，需要的朋友参考下吧...2020-06-25
- 这篇文章主要给大家介绍了关于利用Python验证的50个常见正则表达式的相关资料，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-03-11
- 这篇文章主要介绍了PHP正则表达式过滤html标签属性的相关内容，实用性非常，感兴趣的朋友参考下吧...2016-05-06
- 在本篇文章里小编给大家整理的是一篇关于js用正则表达式筛选年月日的实例方法，对此有兴趣的朋友们可以学习下。...2021-01-04
- layui的正则表达式是在form表单中完成的，这篇文章主要介绍了layui 正则表达式验证使用教程，本文通过实例代码给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-05-07
javascript 手机号码正则表达式验证函数 <font color=red>原创</font>
随着手机号码段的不断增加,以前网上的手机号码验证函数都不能那么完美的支持了，这里脚本之家编辑特为大家准备的一个简单的正则与手机验证的函数分析。...2021-05-07