一行正則表達式判斷質數的代碼

Posted on by

背景

昨天無意中看到一篇大佬的文章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))
}

代碼邏輯非常簡單，生成"1" * n長度的字符串，通過/^1?$|^(11+?)\1+$/正則表達式進行判斷，再將結果取反

正則分析

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

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

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

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

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

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

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

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

步驟 匹配結果 說明
step 1 1 1 1 1 1 1 1 1 1 (11+?)匹配到"11"
step 2 1 1 1 1 1 1 1 1 1 分組結果賦值給\1，那麼正則就變成 "11"+$，繼續匹配剩餘的字符(7個"1")
step 3 1 1 1 1 1 1 1 1 1 再重復3輪的匹配，發現剩餘一個"1"，不滿足$，進行回溯
step 4 1 1 1 1 1 1 1 1 1 還是不滿足$，繼續回溯
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 分組結果賦值給\1，那麼正則就變成 "111"+$，繼續匹配剩餘的字符(6個"1")
step 7 1 1 1 1 1 1 1 1 1 再重復2輪的匹配，滿足$，匹配成功

原理

經過上述的分析，不難發現，其實回溯就是將數字不斷除於2、3、4….，最後檢查是否有餘數，沒有的話就匹配成功（非質數），非常簡單粗暴的窮舉法

優化空間

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

耗時上減少瞭接近一半

總結

其實這個正則性能非常差（窮舉法），實用性不高，但是思路很讓人驚艷

到此這篇關於一行正則表達式判斷質數的文章就介紹到這瞭,更多相關正則表達式判斷質數內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：