背景

昨天無(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+$

原理

經(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)有必要，那么正則可以改寫成這樣/^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)文章希望大家以后多多支持腳本之家！

最新評(píng)論