正規表現で素数判定

追記：ハッキリ言ってこの正規表現はネタなので，実際に素数判定を行いたい場合は，もっと別な賢いアルゴリズムを使ったほうが良いです

正規表現で素数が判定できるという記事を見たので試してみた．
http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/

この記事によると

/^1?$|^(11+?)\1+$/

という正規表現を使うと，素数判定が出来るらしい．ある整数 n が素数かどうか判定したい場合は，"1" * nという文字列がこの正規表現にマッチするかどうかを調べればよく，マッチすれば非素数，マッチしなければ素数となる．ただし，"1" * n は，例えば，n が 4 ならば "1111" と 1 が 4 回連続して続く文字列となる．

Rubyで書いた素数判定プログラムはこんな感じになるそうだ．

def is_prime(n)
    ("1" * n) !~ /^1?$|^(11+?)\1+$/
end

元記事の真似をして，irbで試してみる．

$ irb
>> def is_prime(n)
>> ("1" * n) !~ /^1?$|^(11+?)\1+$/
>> end
>> nil
>> is_prime(10)
>> false
>> is_prime(7)
>> true
>> is_prime(9)
>> false
>> is_prime(97)
>> true

すごい．本当に判定出来ている．にわかには信じ難い光景である．この正規表現を分解してみてみる．

この正規表現を見てみると．

/^1?$|^(11+?)\1+$/

となっているが，これは，

/^1?$/

と

/^(11+?)\1+$/

の2つに分けて考えることが出来る．このどちらかにマッチすれば，非素数という事になるので，順に見ていく．

^1?$

次の正規表現

/^1?$/

であるが，^は行頭を，?は直前の正規表現の0回か1回の繰り返しを，$は行末を表す正規表現であり，これはよく使うシンタックスなので特に問題ないと思う．この正規表現がマッチするのは，"1"か，から文字の""となる．すなわち，1 か 非整数値の場合は非素数と判定するために使われるパターンであることが分かる．

^(11+?)\1+$

問題は次の正規表現となる．

/^(11+?)\1+$/

^，$は，やはり行頭と行末を表しており特に問題ない．特に重要なのは \1 であるが，そのまえに，

/^11+?/

について考えてみる．()は外してあるが，これは \1 と関係するのでこれもあとで考える．

+? についてだが，これは，直前の正規表現の1回以上の繰り返しを表す．ただし，マッチングは最短一致で行われる．つまり，"11110" と 言う文字列があった場合，マッチするのは先頭2文字の"11"となる．

ちなみに，+ だと最長一致となり，"11110" という文字列の場合は，"1111"がマッチすることになる．

次はいよいよ "/^(11+?)\1+$/" である．\1 は後方参照に使われるらしい．使い方は，Rubyの正規表現マニュアルを見ると一発でわかる．
http://www.ruby-lang.org/ja/man/html/_C0B5B5ACC9BDB8BD.html#a.b8.e5.ca.fd.bb.b2.be.c8

re = /(foo|bar|baz)\1/
p re =~ 'foofoo'   # => 0
p re =~ 'barbar'   # => 0
p re =~ 'bazbaz'   # => 0
p re =~ 'foobar'   # => nil

つまり，\1 は 1 番目の括弧 ( ) にマッチした文字列にマッチすることになる．

ここまで来てようやく謎が解けた．つまりこれは，2 から n - 1 まで順に割り算していき，割り切れたら非素数，割り切れなかったら素数と判定しているのと同じことだったのだ．

例

n = 8 の場合．

マッチ用の文字列は"11111111"となる．

まずはじめに，

/^11+?/

が検査される．最短一致なので，一致する文字列は，先頭の"11"となる．

次に，残りの後ろ6文字の"111111"が

/(11)+$/

というパターンと照合される．"111111"は，11を3回連続することで書くことが出来るためパターンマッチに成功することになる．従って，8は非素数となる．偶数の場合は，全てここで処理が終了して非素数と判定される．

n = 9 の場合

マッチ用の文字列は"111111111"となる．

まずはじめに，

/^11+?/

が検査される．最短一致なので，一致する文字列は，先頭の"11"となる．

同じく，残りの後ろ7文字の"1111111"が

/(11)+$/

というパターンと照合される．しかしながら，7文字であるため，11の繰り返しで書くことが出来ず，照合は失敗する．

ここで重要なのは，

/^11+?/

が一致するのは，"11"のみではなく，"111"や，"1111"やそれ以上の繰り返しも含まれるということである．従って，このパターンは先頭3文字の"111"と一致し，残りの後ろ6文字の"111111"が

/(111)+$/

というパターンと照合される．すると，これは照合に成功するため，9は非素数と判定される．

n = 7 の場合

ここまで来たら分かるとおり，n = 7，"1111111"の場合は，まずはじめに

/^11+?/

が検査されて，先頭2文字の"11"がマッチする．そのため，残りの後ろ 5 文字の "11111"と，

/(11)+$/

が照合されるが，これは失敗する．
ところで

/^11+?/

という正規表現は，先頭の"111", ともマッチするため，今度は後ろの残り 4 文字の"1111"と

/(111)+$/

が照合されることになる．しかしながら，これもまた失敗する．

あとはこれの繰り返しであるが，7 は素数であるので，永遠にパターンとマッチすることはなく，無事に素数と判定される．


正規表現でエラトステネスのふるいはさすがに無理かな