檢查素?cái)?shù)與否的正則表達(dá)式
要使用這個(gè)正規(guī)則表達(dá)式，你需要把自然數(shù)轉(zhuǎn)成多個(gè)1的字符串，如：2 要寫(xiě)成 “11”， 3 要寫(xiě)成 “111”, 17 要寫(xiě)成“11111111111111111”，這種工作使用一些腳本語(yǔ)言可以輕松的完成。
一開(kāi)始我對(duì)這個(gè)表達(dá)式持懷疑態(tài)度，但仔細(xì)研究了一下這個(gè)表達(dá)式，發(fā)現(xiàn)是非常合理的，下面，讓我?guī)銇?lái)細(xì)細(xì)剖析一下是這個(gè)表達(dá)式的工作原理。
首先，我們看到這個(gè)表達(dá)式中有“|”，也就是說(shuō)這個(gè)表達(dá)式可以分成兩個(gè)部分：/^1?$/ 和 /^(11+?)\1+$/
可見(jiàn)這個(gè)正規(guī)則表達(dá)式是取非素?cái)?shù)，要得到素?cái)?shù)還得要對(duì)整個(gè)表達(dá)式求反。通過(guò)上面的分析，我們知道，第二部分是最重要的，對(duì)于第二部分，舉幾個(gè)例子，
示例一：判斷自然數(shù)8。我們可以知道，8轉(zhuǎn)成我們的格式就是“11111111”，對(duì)于(11+?)，其匹配了“11”，于是還剩下“111111”，而\1+$正好匹配了剩下的“111111”，因?yàn)椋?1”這個(gè)模式在“111111”出現(xiàn)了三次，符合模式匹配，返回true。所以，匹配成功，于是這個(gè)數(shù)不是質(zhì)數(shù)。
示例二：判斷自然數(shù)11。轉(zhuǎn)成我們需要的格式是“11111111111”（十一個(gè)1），對(duì)于(11+?)，其匹配了“11”（前兩個(gè)1），還剩下“111111111”（九個(gè)1），而\1+$無(wú)法為“11”匹配那“九個(gè)1”，因?yàn)椤?1”這個(gè)模式并沒(méi)有在“九個(gè)1”這個(gè)串中正好出現(xiàn)N次。于是，我們的正則表達(dá)式引擎會(huì)嘗試下一種方法，先匹配“111”（前三個(gè)1），然后把“111”作為模式去匹配剩下的“11111111”（八個(gè)1），很明顯，那“八個(gè)1”并沒(méi)有匹配“三個(gè)1”多次。所以，引擎會(huì)繼續(xù)向下嘗試……直至嘗試所有可能都無(wú)法匹配成功。所以11是素?cái)?shù)。
通過(guò)示例二，我們可以得到這樣的等價(jià)數(shù)算算法，正則表達(dá)式會(huì)匹配這若干個(gè)1中有沒(méi)有出現(xiàn)“二個(gè)1”的整數(shù)倍，“三個(gè)1”的整數(shù)倍，“四個(gè)1”的整數(shù)倍……，而，這正好是我們需要的算素?cái)?shù)的算法。現(xiàn)在大家明白了吧。
下面，我們用perl來(lái)使用這個(gè)正規(guī)則表達(dá)式不停地輸出素?cái)?shù)：（關(guān)于perl的語(yǔ)法我就不多說(shuō)了，請(qǐng)注意表達(dá)式前的取反操作符）
perl -e'$|++;(1 x$_)!~/^1?$|^(11+?)\1+$/print"$_ "while ++$_'
另外，讓我們來(lái)舉一反三，根據(jù)上述的這種方法，我們甚至可以用正則表達(dá)式來(lái)求證某方式是否有解，如：
大家不妨自己做做練習(xí)，為什么上述的兩個(gè)正則表達(dá)式可以判斷方程是否有解。如果無(wú)法參透其中的奧妙的話，你可以讀讀這篇英文文章。
標(biāo)簽：綿陽(yáng) 銅川 無(wú)錫 泰州 長(zhǎng)沙 宣城 西安 重慶
巨人網(wǎng)絡(luò)通訊聲明：本文標(biāo)題《檢查素?cái)?shù)的正則表達(dá)式分享》，本文關(guān)鍵詞 檢查,素?cái)?shù),的,正則,表達(dá)式,；如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問(wèn)題，煩請(qǐng)?zhí)峁┫嚓P(guān)信息告之我們，我們將及時(shí)溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò)，涉及言論、版權(quán)與本站無(wú)關(guān)。
