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

目录
  • 背景
  • 示例
  • 正则分析
  • 原理
  • 优化空间
  • 性能测试
  • 总结

背景

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

耗时上减少了接近一半

总结

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

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

(0)

相关推荐

  • 判断颜色是否合法的正则表达式(详解)

    "^#([0-9a-fA-F]{6}|[0-9a-fA-F]{3})$"; 意思是:以#开头,后面是数字和a-f的字符(大写或小写),这个值是6位或3位.要匹配一个3为是为了符合css颜色的简写规则: "#abc"=="#aabbcc" 注意:如果需要进行16位和10位的转换,比如将颜色值转成int存在数据库,如果是6位的颜色没问题,如果是3位的颜色就有问题了,因为当你取回来从10进制转为 16进制的时候,你不知道他应该是3位还是6位. 比如:#

  • 用正则表达式来判断素数的代码

    复制代码 代码如下: import re def is_prime(num): return not re.match(r"^1?$|^(11+?)\1+$", '1' * num) 这个正则表达式实际上表示所有合数长度的"1"串(还包括特例"1"). (11+?)表示所有大于等于2的整数,后面接着的\1+表示重复一次以上--这不就是所有合数吗--

  • 正则表达式(RegExp)判断文本框中是否包含特殊符号

    前言 有时,我们希望判断文本框中用户输入的字符是否含有特殊符号(*/#$@),就像用户注册时密码框的填写. demo 利用 RegExp 对象,能很优雅的实现以上需求: // even(文本框内容) function (even) { // 规则对象(flag) var flag = new RegExp("[`~!@#$^&*()=|{}':;',\\[\\].<><>/?~!@#¥--&*()--|{}[]'::""'.,.? ]&

  • JS使用正则表达式判断输入框失去焦点事件

    效果图 项目的正则表达式规则 1:用户名: 大写字母开头 6-20位字符(不允许有符号但是允许有_) 2:密码 大写开头 数字字母符号混合 8-15位 3:确认密码 大写开头 数字字母符号混合 8-15位 4:邮箱 邮箱格式 5:手机号 手机号格式 6:身份证号 身份证号格式 7:地址 中文开头 数字 - 字母 中文混合 项目目录 html代码 由于无法上传bootstrap.min.css 需要样式的需要前往官网下载 bootstrap中文网 <!DOCTYPE html> <html

  • 判断时间的正则表达式

    普通方法为,分离出小时.分钟.秒分别进行判断: public static boolean timeCheck(String time, String owner) { //检查时间字符串time是否满足格式"HH:mm:ss"或"HH:mm",若不满足显示相应消息,并返回false if(time.equals("")){ String msg = owner+" : "+"Time is EMPTY."

  • 使用正则表达式判断密码强弱

    学python的re模板,写了个文章发现没人看,所以总结出来经验,理论没人爱,实战的人心,那么既然没人喜欢理论就直接上实战,在实战中精炼理论.不多说直接先上代码 def password_level(password): weak = re.compile(r'^((\d+)|([A-Za-z]+)|(\W+))$') level_weak = weak.match(password) level_middle = re.match(r'([0-9]+(\W+|\_+|[A-Za-z]+))+|

  • 正则表达式号码靓号类型判断代码

    靓号检测:主要可以检测连号(正连 12345.倒连65432).AABB号.手机号码.日期号(生日号.年度号).ABBCABB号,3位以上重复号.更多类型号码检测可以根据以下表达式改造. ' 匹配6位顺增 regex.Pattern = "(?:0(?=1)|1(?=2)|2(?=3)|3(?=4)|4(?=5)|5(?=6)|6(?=7)|7(?=8)|8(?=9)){5}\d" ' 匹配6位顺降 regex.Pattern = "(?:9(?=8)|8(?=7)|7(?=

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

    目录 背景 示例 正则分析 原理 优化空间 性能测试 总结 背景 昨天无意中看到一篇大佬的文章Primality regex(正则表达式判断质数),惊为天人,正则表达式也能用来判断质数了?立马来研究下 示例 perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' [number] 翻译成JS代码如下 function isPrime(n) { return !/^1?$|^(11+?)\1+$/.test("

  • JS 正则表达式判断各个浏览器代码详解

    注释都在代码里面了.很详细. 只判断了IE 火狐 谷歌 因为我没装其他浏览器了,所以呵呵.当然如果要判断其他浏览器.基本代码都是一样的了. 复制代码 代码如下: (function(){ window.sys={}; var ua=navigator.userAgent.toLowerCase(); //首先我们来看一下3个浏览器都返回了什么看下面. //ie ua=mozilla/4.0 (compatible; msie 8.0; windows nt 5.2; trident/4.0; q

  • JS正则表达式判断有效数实例代码

    <script type="text/javascript"> function validate(){ var reg = new RegExp("^[0-9]*$"); var obj = document.getElementById("name"); if(!reg.test(obj.value)){ alert("请输入数字!"); } if(!/^[0-9]*$/.test(obj.value)){ a

  • IOS中用正则表达式判断输入的内容为8-16位且同时包含数字和字母

    今天在项目中需要用到判断用户输入的用户名长度为8-16位且同时包含数字和字母,在网上搜了一下正则表达式的用法,然后参考这篇文章,完美解答了问题.记录一下: 密码有如下要求:由数字和字母组成,并且要同时含有数字和字母,且长度要在8-16位之间. 如何分析需求?拆分!这就是软件设计的一般思路了.于是乎,拆分需求如下: 1,不能全部是数字 2,不能全部是字母 3,必须是数字或字母 只要能同时满足上面3个要求就可以了,写出来如下: ^(?![0-9]+$)(?![a-zA-Z]+$)[0-9A-Za-z

  • C#正则表达式判断输入日期格式是否正确

    本文将介绍一段实例代码,来讲解利用正则表达式使C#判断输入日期格式是否正确的方法.希望这段代码能对大家有所帮助. 通常我们在用C#编写系统程序或者Web开发时,都会遇到需要验证输入的字符串是否是日期的情况,下面为大家介绍一种非常全面的用正则表达式验证日期的方法: c 正则表达式日期代码一: /// <summary> /// 是否为日期型字符串 /// </summary> /// <param name="StrSource">日期字符串(2008

  • 使用正则表达式判断是否为手机号码(简单且实用)

    下面一段代码是关于正在表达式判断是否为手机号码的代码,具体代码如下所述: public static boolean isMobileNO(String mobile) { Pattern p = Pattern .compile("^((13[0-9])|(15[^4,\\D])|(18[0-9]))\\d{8}$"); Matcher m = p.matcher(mobile); return m.matches(); } 以上所述是小编给大家介绍的使用正则表达式判断是否为手机号码

  • iOS 正则表达式判断纯数字及匹配11位手机号码的方法

    第一种使用正则表达式 判断 //是否是纯数字 + (BOOL)isNumText:(NSString *)str{ NSString * regex = @"(/^[0-9]*$/)"; NSPredicate * pred = [NSPredicate predicateWithFormat:@"SELF MATCHES %@", regex]; BOOL isMatch = [pred evaluateWithObject:str]; if (isMatch)

  • 利用正则表达式判断一个给定的字符是否是回文

    如果给定的字符串是回文,返回true,反之,返回false. 如果一个字符串忽略标点符号.大小写和空格,正着读和反着读一模一样,那么这个字符串就是palindrome(回文). 注意你需要去掉字符串多余的标点符号和空格,然后把字符串转化成小写来验证此字符串是否为回文. 函数参数的值可以为"racecar","RaceCar"和"race CAR". 关键代码: 去掉字符串中的标点符号和空白格.可以用str.replace()+正则表达式匹配. v

  • IOS正则表达式判断输入类型(整理)

    在开发过程中,有时需要对用户输入的类型做判断,最常见是在注册页面即用户名和密码,代码整理如下: 只能为中文 -(BOOL)onlyInputChineseCharacters:(NSString*)string{ NSString *zhString = @"[\u4e00-\u9fa5]+"; NSPredicate *predicate = [NSPredicate predicateWithFormat:@"SELF MATCHES %@",zhString]

随机推荐