一行正则表达式判断质数的代码
<div id="navCategory"><h5 class="catalogue">目录</h5><ul class="first_class_ul"><li><a href="#_label0">背景</a></li><li><a href="#_label1">示例</a></li><li><a href="#_label2">正则分析</a></li><li><a href="#_label3">原理</a></li><li><a href="#_label4">优化空间</a></li><li><a href="#_label5">性能测试</a></li><li><a href="#_label6">总结</a></li></ul></div><p class="maodian"><a name="_label0"></a></p><h2>背景</h2><p>昨天无意中看到一篇大佬的文章<a href="http://montreal.pm.org/tech/neil_kandalgaonkar.shtml" target="_blank">Primality regex</a>（<strong>正则表达式判断质数</strong>），惊为天人，正则表达式也能用来判断质数了？立马来研究下</p>
<p class="maodian"><a name="_label1"></a></p><h2>示例</h2>
<div class="jb51code"><pre class="brush:bash;">perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' </pre></div>
<p>翻译成JS代码如下</p>
<div class="jb51code"><pre class="brush:js;">function isPrime(n) {
return !/^1?$|^(11+?)\1+$/.test("1".repeat(n))
}</pre></div>
<p>代码逻辑非常简单，生成<code>"1" * n</code>长度的字符串，通过<code>/^1?$|^(11+?)\1+$/</code>正则表达式进行判断，再将结果取反</p>
<p class="maodian"><a name="_label2"></a></p><h2>正则分析</h2>
<div class="jb51code"><pre class="brush:plain;">/^1?$|^(11+?)\1+$/</pre></div>
<p>上面正则表达式有2个分支，分别是</p>
<ul><li><code>/^1?$</code></li><li><code>^(11+?)\1+$</code></li></ul>
<p>分支1 逻辑很简单，就是匹配0或者1个 <code>"1"</code>，因为要排除数字<code>1</code>（非质数）</p>
<p>分支2 就有意思了，可以拆成2块来看</p>
<ul><li><code>^(11+?)</code></li><li><code>\1+$</code></li></ul>
<p>表达式1，非贪婪模式下匹配 <code>"11" "111" "1111"....</code>，作为一个分组<br />表达式2，<code>\1</code>代表将表达式1匹配的结果赋值给<code>\1</code>，判断是否结尾，否的话会触发回溯（因为表达式1可能匹配多种情况）</p>
<p>举个例子就更清晰了，比如传入n = 9，分支1不满足可以直接忽略<br /><code>^(11+?)\1+$</code></p>
<table><tbody><tr><th>步骤</th><th>匹配结果</th><th>说明</th></tr><tr><td>step 1</td><td><strong>1 1</strong> 1 1 1 1 1 1 1</td><td><code>(11+?)</code>匹配到<code>"11"</code></td></tr><tr><td>step 2</td><td><strong>1 1</strong> 1 1 1 1 1 1 1</td><td>分组结果赋值给<code>\1</code>，那么正则就变成 "11"+$，继续匹配剩余的字符(7个"1")</td></tr><tr><td>step 3</td><td><strong>1 1 1 1 1 1 1 1</strong> 1</td><td>再重复3轮的匹配，发现剩余一个"1"，不满足$，进行回溯</td></tr><tr><td>step 4</td><td><strong>1 1 1 1 1 1 1</strong> 1 1</td><td>还是不满足$，继续回溯</td></tr><tr><td>step 5</td><td><strong>1 1 1</strong> 1 1 1 1 1 1</td><td>一直回溯到<code>step 1</code>，<code>(11+?)</code>匹配到<code>"111"</code></td></tr><tr><td>step 6</td><td><strong>1 1 1</strong> 1 1 1 1 1 1</td><td>分组结果赋值给<code>\1</code>，那么正则就变成 "111"+$，继续匹配剩余的字符(6个"1")</td></tr><tr><td>step 7</td><td><strong>1 1 1 1 1 1 1 1 1</strong></td><td>再重复2轮的匹配，满足$，匹配成功</td></tr></tbody></table>
<p class="maodian"><a name="_label3"></a></p><h2>原理</h2>
<p>经过上述的分析，不难发现，其实<strong>回溯就是将数字不断除于2、3、4....</strong>，最后检查是否有余数，没有的话就匹配成功（非质数），非常简单粗暴的穷举法</p>
<p class="maodian"><a name="_label4"></a></p><h2>优化空间</h2>
<p>仔细看正则匹配的过程分析，其实<code>step 3 ~ step 4</code>的回溯完全没有必要，那么正则可以改写成这样<code>/^1?$|^(11+?)\1+?$/</code>，将<code>\1+</code>改成非贪婪模式<code>\1+?</code>，那么就放弃step 4回溯</p>
<p class="maodian"><a name="_label5"></a></p><h2>性能测试</h2>
<div class="jb51code"><pre class="brush:plain;">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</pre></div>
<p>耗时上减少了接近一半</p>
<p class="maodian"><a name="_label6"></a></p><h2>总结</h2>
<p>其实这个正则性能非常差（穷举法），实用性不高，但是思路很让人惊艳</p>
頁:
[1]