一行正則表達式判斷質(zhì)數(shù)的代碼

更新時間：2022年05月26日 16:22:52 作者：jayzou

這篇文章主要介紹了一行正則表達式判斷質(zhì)數(shù),其實這個正則性能非常差（窮舉法），實用性不高，但是思路很讓人驚艷，需要的朋友可以參考下

背景

昨天無意中看到一篇大佬的文章Primality regex（正則表達式判斷質(zhì)數(shù)），驚為天人，正則表達式也能用來判斷質(zhì)數(shù)了？立馬來研究下

示例

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+$/正則表達式進行判斷，再將結(jié)果取反

正則分析

/^1?$|^(11+?)\1+$/

上面正則表達式有2個分支，分別是

/^1?$
^(11+?)\1+$

分支1 邏輯很簡單，就是匹配0或者1個 "1"，因為要排除數(shù)字1（非質(zhì)數(shù)）

分支2 就有意思了，可以拆成2塊來看

^(11+?)
\1+$

表達式1，非貪婪模式下匹配 "11" "111" "1111"....，作為一個分組
表達式2，\1代表將表達式1匹配的結(jié)果賦值給\1，判斷是否結(jié)尾，否的話會觸發(fā)回溯（因為表達式1可能匹配多種情況）

舉個例子就更清晰了，比如傳入n = 9，分支1不滿足可以直接忽略
^(11+?)\1+$

步驟	匹配結(jié)果	說明
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個"1")
step 3	1 1 1 1 1 1 1 1 1	再重復3輪的匹配，發(fā)現(xiàn)剩余一個"1"，不滿足$，進行回溯
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個"1")
step 7	1 1 1 1 1 1 1 1 1	再重復2輪的匹配，滿足$，匹配成功

原理

經(jīng)過上述的分析，不難發(fā)現(xiàn)，其實回溯就是將數(shù)字不斷除于2、3、4....，最后檢查是否有余數(shù)，沒有的話就匹配成功（非質(zhì)數(shù)），非常簡單粗暴的窮舉法

優(yōu)化空間

仔細看正則匹配的過程分析，其實step 3 ~ step 4的回溯完全沒有必要，那么正則可以改寫成這樣/^1?$|^(11+?)\1+?$/，將\1+改成非貪婪模式\1+?，那么就放棄step 4回溯

性能測試

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

耗時上減少了接近一半