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

[art1 (人，原來不是人)]

  http://vimcasts.org/episodes/vimgolf-prime-numbers/

  這原本是 vimgolf 的題目，但解法很有意思，因此作者特別介紹，也找出最初的出處

  首先要把每個數改用符號表示，像是 1 就用一個 *，2 就用 **，3 就用 ***
  這連結的解法是用 Tab，最早出處是用 1

  最主要的部份
  (<Tab><Tab>+)\1+
  最早出處則是 (11+?)\1+

  目前的理解是括號內要找的是從二開始遞增的數，\1 則是括號找到的數的倍數
  有倍數肯定不是質數

  兩個解法差了一個 ?，我猜有加 ? 的效能應該比較好？

--
   「看在上帝的份上，我們不能當著孩子的面槍殺他的父親！」
   「那我們就連孩子一起幹掉！」
   「第一槍打中的是那個天真的孩子，第二槍是抱著孩子的母親。第三槍
     停頓了三秒，當難以致信的父親擦拭著臉上愛子的腦漿從震驚中醒轉
     過來，慢慢的轉頭看向停車的地方，分辨出是誰在攻擊他後，第三顆
     子彈才將他的腦殼打飛。」                       ─摘自〈狼群〉

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.173.33.68 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/RegExp/M.1664128166.A.3D7.html
※ 編輯: art1 (218.173.33.68 臺灣), 09/26/2022 01:49:47
※ 編輯: art1 (218.173.33.68 臺灣), 09/26/2022 02:16:08
推 OSDBNetwork: + 後面的 ? 應該是指 Lazy Quantifier
推 LPH66: 對, 這裡的 Lazy 用來讓因數從小的開始試
→ LPH66: 11+? 會先配出 11 當做 \1 後試著配對 \1+
→ LPH66: 如果成功那就是 2 的倍數, 不成功的話倒回會倒到 +? 這裡
→ LPH66: 然後延長一個試, 所以就會試 111 當做 \1 來配對 \1+
→ LPH66: 在這裡成功就是 3 的倍數, 依此類推
→ LPH66: 基本上就是連結裡的圖從下面試上去
→ LPH66: 那當數字有小因數時會比較快結束
→ glo6e: 推