目录背景示例正则分析原理优化空间性能测试总结
昨天无意中看到一篇大佬的文章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))
}
return !/^1?$|^(11+?)\1+$/.test(“1”.repeat(n))
}
代码逻辑非常简单，生成长度的字符串，通过正则表达式进行判断，再将结果取反
/^1?$|^(11+?)\1+$/
上面正则表达式有2个分支，分别是
分支1 逻辑很简单，就是匹配0或者1个 ，因为要排除数字（非质数）
分支2 就有意思了，可以拆成2块来看
表达式1，非贪婪模式下匹配 ，作为一个分组
表达式2，代表将表达式1匹配的结果赋值给，判断是否结尾，否的话会触发回溯（因为表达式1可能匹配多种情况）
举个例子就更清晰了，比如传入n=9，分支1不满足可以直接忽略
步骤匹配结果说明step 11 1 1 1 1 1 1 1 1匹配到step 21 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 61 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 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
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使用正则表达式判断输入框失去焦点事件使用正则表达式判断密码强弱判断颜色是否合法的正则表达式(详解)正则表达式号码靓号类型判断代码判断时间的正则表达式用正则表达式来判断素数的代码
© 版权声明
文章版权归作者所有，未经允许请勿转载。
相关文章
