判斷字串長度是否為質數的正規表示式

讀到一個神奇的正規表示式， 竟然可以拿來判斷字串長度是否為質數？！
^x?$|^(xx+?)\1+$
"|" 的左邊很簡單， 只是在比對長度為0或者1的字串。

比較燒腦的右邊則是在嘗試比對 「長度恰好為 p*(q+1)」 的字串。 小括弧裡面的部分抓取 「長度至少為2的子串， 越短越好」。 這裡用 non-greedy 的 +? 而不是較常見的 (greedy 的) + 來表達「越短越好」。 後面的 \1+ 表示 「重複前面小括弧比對成功的同一字串任意次， 至少1次」。 如果小括弧內的字串長度為 p， 後面的成功比對次數為 q， 那麼整個字串的長度就是 p*(q+1)， 不是質數。

用 python 寫， 程式長這樣：

import re
def is_prime(n):
    return not re.match(r'^x?$|^(xx+?)\1+$', 'x'*n)

def primes_up_to(n):
    return [ i for i in range(n) if is_prime(i) ]

primes_up_to(100)

這一篇 有更詳細的解說。