怎么用javascript正則表達式判斷質(zhì)數(shù)

這篇文章主要介紹“怎么用javascript正則表達式判斷質(zhì)數(shù)”，在日常操作中，相信很多人在怎么用javascript正則表達式判斷質(zhì)數(shù)問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”怎么用javascript正則表達式判斷質(zhì)數(shù)”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

示例

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+$

原理

經(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

耗時上減少了接近一半

到此，關(guān)于“怎么用javascript正則表達式判斷質(zhì)數(shù)”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>