[閒聊] 原來正規表示法可以用來找質數

作者: art1 (人,原來不是人)   2022-09-26 01:49:22
http://vimcasts.org/episodes/vimgolf-prime-numbers/
這原本是 vimgolf 的題目,但解法很有意思,因此作者特別介紹,也找出最初的出處
首先要把每個數改用符號表示,像是 1 就用一個 *,2 就用 **,3 就用 ***
這連結的解法是用 Tab,最早出處是用 1
最主要的部份
(<Tab><Tab>+)\1+
最早出處則是 (11+?)\1+
目前的理解是括號內要找的是從二開始遞增的數,\1 則是括號找到的數的倍數
有倍數肯定不是質數
兩個解法差了一個 ?,我猜有加 ? 的效能應該比較好?
作者: OSDBNetwork (路人甲)   2022-09-26 16:36:00
+ 後面的 ? 應該是指 Lazy Quantifier
作者: LPH66 (-6.2598534e+18f)   2022-09-26 19:22:00
對, 這裡的 Lazy 用來讓因數從小的開始試11+? 會先配出 11 當做 \1 後試著配對 \1+如果成功那就是 2 的倍數, 不成功的話倒回會倒到 +? 這裡然後延長一個試, 所以就會試 111 當做 \1 來配對 \1+在這裡成功就是 3 的倍數, 依此類推基本上就是連結裡的圖從下面試上去那當數字有小因數時會比較快結束
作者: glo6e (ezdodance)   2022-12-25 22:52:00

Links booklink

Contact Us: admin [ a t ] ucptt.com