Regex Golf をやってみた 9 〜素数にリベンジ〜

Regex Golf 9回目（8回目はこちら）

正規表現によるパズルゲーム？ Regex Golf 7問目 "Prime" ですが、昨日すっきりしない感じで終えたので今日はリベンジです。

以下、ネタバレ

さて、昨日は "x" の素数回繰り返しを検索するのではなく、素数でないものを否定する方向でこんな風にしました。

^(?!((xx){2,}|(xxx){2,}|(x{5}){2,})$)

考え方としては

• 「素数」の2回以上繰り返しがあればダメ
•  問題の数が限られているから正解になるまで素数を足していけばOK

という物でした。

今日はもう少し基本に立ち返って考えます。そもそも素数とは Wikipedia によると

素数（そすう、英: prime number）とは、1 と自分自身以外に正の約数を持たない自然数で、1 でない数のことである。

という事ですから、素数でない数は

• 1 は素数ではない
• 割ると2以上になる数が存在する数は素数ではない

と言うことになります。
前回は「素数の2回以上繰り返し」つまり「素数で割ると2以上になる」ものを素数ではないと判断しましたが、この「素数」は必要ない事がわかります。

どうなるかと言うと

• "x" 1 文字は素数ではない
• ^(?!x$)
• 割ると2以上になる数が存在する数は素数ではない
  つまり "x" 2 文字以上の 2 回以上繰り返しは "x" 素数個の文字列ではない
• ^(?!(xx+)\1+$)

合わせると

^(?!(x|(xx+)\2+)$)

となります。

かなりスッキリ！恐らく正解でしょう！！

後は短く出来るか？ですが "x" 1 文字は問題の中にないので削ることが出来ます。

^(?!(xx+)\1+$)

いや〜
ちゃんと出来ると気分爽快ですね！！

ちなみに "x" 2 文字以上の 2 回以上繰り返しは

(xx+){2,}

一瞬と書けそうな気がしましたがそれはつまり

(xx+)(xx+)(|xx+)(|xx+)(|xx+) ...

とこんな感じになり、括弧内の "x" 文字数は括弧ごとに違ってOKになってしまうため今回意図している検索にはなりません。
そもそも文字数も増えてますし…

次回、10回目は 8 問目、 "Four" の予定です！