一行正则表达式判断质数的代码

 更新时间:2022-08-04 01:14:21   作者:佚名   我要评论(0)

目录背景示例正则分析原理优化空间性能测试总结背景
昨天无意中看到一篇大佬的文章Primality regex(正则表达式判断质数),惊为天人,正则表

背景

昨天无意中看到一篇大佬的文章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 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

耗时上减少了接近一半

总结

其实这个正则性能非常差(穷举法),实用性不高,但是思路很让人惊艳

到此这篇关于一行正则表达式判断质数的文章就介绍到这了,更多相关正则表达式判断质数内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家!

您可能感兴趣的文章:
  • 正则表达式(RegExp)判断文本框中是否包含特殊符号
  • JS使用正则表达式判断输入框失去焦点事件
  • 使用正则表达式判断密码强弱
  • 判断颜色是否合法的正则表达式(详解)
  • 正则表达式号码靓号类型判断代码
  • 判断时间的正则表达式
  • 用正则表达式来判断素数的代码

相关文章

  • 一行正则表达式判断质数的代码

    一行正则表达式判断质数的代码

    目录背景示例正则分析原理优化空间性能测试总结背景 昨天无意中看到一篇大佬的文章Primality regex(正则表达式判断质数),惊为天人,正则表
    2022-08-04
  • 正则表达式之字符串模式匹配实例详解

    正则表达式之字符串模式匹配实例详解

    目录前言什么是正则表达式字符范围匹配元字符多次重复匹配定位匹配贪婪模式与非贪婪模式表达式分组结语前言 今天我们来学习正则表达式,正则
    2022-08-04
  • 正则表达式中问号(?)的正确用法详解

    正则表达式中问号(?)的正确用法详解

    目录1、直接跟随在子表达式后面2、非贪婪匹配3、非获取匹配4、断言参考资料:正则表达式中“?”的用法大概有以下几种 1、直接跟随
    2022-08-04
  • 利用正则表达式匹配浮点型数据

    利用正则表达式匹配浮点型数据

    目录前言:正则表达式Java代码附:正则表达式(同时匹配整型数和浮点数)总结前言: 在开发中我们常常会使用到正则表达式,但很奇怪的是,每
    2022-08-04
  • jsp中文乱码问题的简单解决方法

    jsp中文乱码问题的简单解决方法

    简单解决jsp中文乱码问题 初学jsp制作一个简单的响应页面 具体代码如下: <form action="test.jsp"> username : <input type="text" nam
    2022-08-04
  • 关于react ant 组件 Select下拉框 值回显的问题

    关于react ant 组件 Select下拉框 值回显的问题

    目录react ant组件Select下拉框值回显问题情形解决得问题react ant-design Select组件下拉框map不显示问题描述问题总结react ant组件Select下
    2022-08-04
  • Java?限制前端重复请求的实例代码

    Java?限制前端重复请求的实例代码

    目录背景及用途实现步骤背景及用途 前端页面出现卡顿,用户反复点击操作按钮,导致后台接口短时间内多次提交 实现步骤 设置切面,增加注解,导
    2022-08-04
  • React路由拦截模式及withRouter示例详解

    React路由拦截模式及withRouter示例详解

    目录一、路由拦截二、路由模式三、withRouter一、路由拦截 在前面两篇 路由博客基础上,我们将ReactRouter.js的我的profile路由设置成路由拦
    2022-08-04
  • Spring超详细讲解IOC与解耦合

    Spring超详细讲解IOC与解耦合

    目录前言一.所谓耦合二.Spring三.核心IOC理解1.容器2.控制反转3.依赖注入四.Bean的实例化1.无参构造2.工厂静态方法3.工厂实例方法(常用)五
    2022-08-04
  • Java与SpringBoot对redis的使用方式

    Java与SpringBoot对redis的使用方式

    目录1.Java连接redis1.1 使用Jedis1.2 使用连接池连接redis1.3 java连接redis集群模式 2.SpringBoot整合redis2.1 StringRedisTemplate2.2 Re
    2022-08-04

最新评论