正規表現で素数判定 - NO!と言えるようになりたい
前からあるネタらしいけど、ここで知った。
^1?$
これは、"1"が0個の場合と1個の場合を検出している。
素数でも合成数でもない非負整数はこの2つだけ。
^(11+?)\1+$
こっちがキモとなる処理で、合成数に過不足なくマッチする。
2個以上並んだ"1"を2回以上繰り返したものと一致する場合があるかのチェック。
a個並んだ"1"をb回繰り返せば、a×b個並んだ"1"になるので、
aとbが2以上の任意の整数をとるなら、文字列「合成数個並んだ"1"」を網羅する。
"?"は、おそらく高速化のためのもので、入ってなくてもいい。
^1?$|^(11+?)\1+$
正規表現を使えるエディタを使うとこの通り、素数の行だけ色が付いてない。
