一行正則表達(dá)式判斷質(zhì)數(shù)的代碼
背景
昨天無(wú)意中看到一篇大佬的文章Primality regex（正則表達(dá)式判斷質(zhì)數(shù)），驚為天人，正則表達(dá)式也能用來(lái)判斷質(zhì)數(shù)了？立馬來(lái)研究下
示例
perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' [number]
翻譯成JS代碼如下
function isPrime(n) {
return !/^1?$|^(11+?)\1+$/.test("1".repeat(n))
}代碼邏輯非常簡(jiǎn)單，生成"1" * n長(zhǎng)度的字符串，通過(guò)/^1?$|^(11+?)\1+$/正則表達(dá)式進(jìn)行判斷，再將結(jié)果取反
正則分析
/^1?$|^(11+?)\1+$/
上面正則表達(dá)式有2個(gè)分支，分別是
/^1?$^(11+?)\1+$
分支1 邏輯很簡(jiǎn)單，就是匹配0或者1個(gè) "1"，因?yàn)橐懦龜?shù)字1（非質(zhì)數(shù)）
分支2 就有意思了，可以拆成2塊來(lái)看
^(11+?)\1+$
表達(dá)式1，非貪婪模式下匹配 "11" "111" "1111"....，作為一個(gè)分組
表達(dá)式2，\1代表將表達(dá)式1匹配的結(jié)果賦值給\1，判斷是否結(jié)尾，否的話會(huì)觸發(fā)回溯（因?yàn)楸磉_(dá)式1可能匹配多種情況）
舉個(gè)例子就更清晰了，比如傳入n = 9，分支1不滿足可以直接忽略^(11+?)\1+$
| 步驟 | 匹配結(jié)果 | 說(shuō)明 |
|---|---|---|
| step 1 | 1 1 1 1 1 1 1 1 1 | (11+?)匹配到"11" |
| step 2 | 1 1 1 1 1 1 1 1 1 | 分組結(jié)果賦值給\1，那么正則就變成 "11"+$，繼續(xù)匹配剩余的字符(7個(gè)"1") |
| step 3 | 1 1 1 1 1 1 1 1 1 | 再重復(fù)3輪的匹配，發(fā)現(xiàn)剩余一個(gè)"1"，不滿足$，進(jìn)行回溯 |
| step 4 | 1 1 1 1 1 1 1 1 1 | 還是不滿足$，繼續(xù)回溯 |
| 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 | 分組結(jié)果賦值給\1，那么正則就變成 "111"+$，繼續(xù)匹配剩余的字符(6個(gè)"1") |
| step 7 | 1 1 1 1 1 1 1 1 1 | 再重復(fù)2輪的匹配，滿足$，匹配成功 |
原理
經(jīng)過(guò)上述的分析，不難發(fā)現(xiàn)，其實(shí)回溯就是將數(shù)字不斷除于2、3、4....，最后檢查是否有余數(shù)，沒(méi)有的話就匹配成功（非質(zhì)數(shù)），非常簡(jiǎn)單粗暴的窮舉法
優(yōu)化空間
仔細(xì)看正則匹配的過(guò)程分析，其實(shí)step 3 ~ step 4的回溯完全沒(méi)有必要，那么正則可以改寫(xiě)成這樣/^1?$|^(11+?)\1+?$/，將\1+改成非貪婪模式\1+?，那么就放棄step 4回溯
性能測(cè)試
console.time('優(yōu)化前')
console.log(!/^1?$|^(11+?)\1+$/.test("1".repeat(33331)));
console.timeEnd('優(yōu)化前')
console.time('優(yōu)化后')
console.log(!/^1?$|^(11+?)\1+?$/.test("1".repeat(33331)));
console.timeEnd('優(yōu)化后')
// true
// 優(yōu)化前: 227.9189453125 ms
// true
// 優(yōu)化后: 155.797119140625 ms耗時(shí)上減少了接近一半
總結(jié)
其實(shí)這個(gè)正則性能非常差（窮舉法），實(shí)用性不高，但是思路很讓人驚艷
到此這篇關(guān)于一行正則表達(dá)式判斷質(zhì)數(shù)的文章就介紹到這了,更多相關(guān)正則表達(dá)式判斷質(zhì)數(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
下面列出了當(dāng)前在 PCRE 中可能使用的修正符。括號(hào)中是這些修正符的內(nèi)部 PCRE 名。修正符中的空格和換行被忽略，其它字符會(huì)導(dǎo)致錯(cuò)誤。2010-07-07
上篇提到了關(guān)于網(wǎng)上流傳查找PHP webshell的python腳本中，不嚴(yán)謹(jǐn)?shù)拇a，并且給出了一個(gè)python的檢測(cè)代碼，同時(shí)，下文里也提到不能檢測(cè)到反引號(hào)的命令執(zhí)行的地方。今天，我想了下，現(xiàn)在把思路發(fā)出來(lái)。2011-04-04
不同的語(yǔ)言或應(yīng)用場(chǎng)景下，正則定義方式、元字符出現(xiàn)的位置不同，轉(zhuǎn)義的方式也是林林總總，不一而同2012-10-10
在實(shí)際例子中學(xué)習(xí)正則表達(dá)式(高效率)
正則表達(dá)式，又稱(chēng)正規(guī)表示法、常規(guī)表示法。下面小編給大家分享幾個(gè)例子給大家講下正則表達(dá)式知識(shí)，非常不錯(cuò)，具有參考借鑒價(jià)值，需要的朋友可以參考下2016-08-08
RegExp 隨筆 JavaScript RegExp 對(duì)象
這篇文章主要介紹了RegExp 隨筆 JavaScript RegExp 對(duì)象,需要的朋友可以參考下2016-10-10
正則表達(dá)式不區(qū)分大小寫(xiě)以及解決思路的探索 .
今天在寫(xiě)一個(gè)正則表達(dá)式的時(shí)候，因?yàn)樽址写笮?xiě)的問(wèn)題，多種大小寫(xiě)的組合，這時(shí)想到了用正則表達(dá)式2014-06-06
這篇文章主要介紹了常用的正則表達(dá)式實(shí)例整理,非常不錯(cuò)，具有參考借鑒價(jià)值，需要的朋友可以參考下2018-03-03
JavaScript 實(shí)現(xiàn)基礎(chǔ) 正則表達(dá)式
正則表達(dá)式用來(lái)從某一段字符串中匹配所需要的字符，這些字符可以非常簡(jiǎn)單，也可以非常復(fù)雜。JavaScript生來(lái)就對(duì)正則表達(dá)式有著良好的支持，在網(wǎng)絡(luò)的字符搜索匹配中發(fā)揮著重要的作用。2009-08-08
這篇文章主要介紹了正則表達(dá)式的字符串替換方法,用到了一些高級(jí)的正則寫(xiě)法，需要的朋友可以參考下2016-01-01
詳解正則表達(dá)式Matcher類(lèi)中g(shù)roup方法
這篇文章主要介紹了正則表達(dá)式Matcher類(lèi)中g(shù)roup方法，本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2019-08-08