先日、正規表現のネタをツイートしたら軽く拡散しました。そこで他にも面白いものあるのかなと調べてみたら素数を判定する正規表現があるという記述を見つけました。
これが実際の正規表現を使った素数判定です↓
const isPrime = (n:number) => !/^.?$|^(..+?)\1+$/.test('0'.repeat(n));
これでなぜ素数を判定できるのかを解説します。
解説
isPrime関数は「長さNの文字列が /^.?$|^(..+?)\1+$/ にマッチするか」を見ています。そして、正規表現にマッチしたらNは合成数、しなければNは素数という判定をしています。
ポイントはやはり正規表現の部分です。
素数判定の正規表現の解説
/^.?$|^(..+?)\1+$/
この正規表現は2つのパートで構成されています。
^.?$^(..+?)\1+$
前者は0と1にマッチし、後者は任意の合成数にマッチします。そのため、コレにマッチしなければ素数となります。
以下それぞれのパートについて解説します。
^.?$ は0と1にマッチする
これは見たままです。0文字または1文字のときにマッチします。簡単ですね。
^(..+?)\1+$ は合成数にマッチする
こっちは一瞥しただけでは分かりません。ただ、ほどいていけばそこまで難しくありません。
まず (..+?) ですが、これは2文字以上にマッチします。そのあとの \1+ は、(..+?)でキャプチャしたグループが1回以上続くことを意味します。つまり、この正規表現は 2文字以上のグループの繰り返しのみで構成されているときにマッチします。
たとえば、 0000 は2つの 00 によって構成されているのでマッチします(=合成数)。逆に、00000 は2文字以上の同じ文字列の繰り返しで構成されていないのでマッチしません(=素数)。
まとめると、この正規表現は文字数が (2以上) x (2以上) で表現できるとき、つまり合成数であるときにマッチします。
まとめ
わかってしまえば案外簡単なロジックで出来ています。面白いですね。
なお、この正規表現は当然ながら効率はよくありません。そのため実用は難しいです。しかし、たった1行で素数判定ができるので、覚えておくといつか役に立つかもしれません。
