なんかすごいですコレ。素数判定する正規表現だとか。完全にネタですねこりゃ。
/^1?$|^(11+?)\1+$/
この正規表現に、素数判定したい数字の値ぶんだけ"1"を連結した文字列をマッチさせます。
つまり3が素数かどうかを判定したい場合、与える文字列は"111"です。
詳しくはコチラを参照。
http://d.hatena.ne.jp/ytakano/20100721/1279736214
どうなってんのこれ
この正規表現の構造を解析してみます。
まず
^1?$
の部分はいいですよね。1かどうかを判定しています。
で、問題のこの部分なわけですが。
^(11+?)\1+$
えーと、"1"が2個以上かつ最小マッチで、それと同じ正規表現が後ろに1個以上続く…ってか。
振る舞いをシミュレートしてみると次のような感じ。("[11...]"は(11+?)が喰う"1"の数を表します)
- [11][11][11]...[11]
- [111][111][111]...[111]
- [1111][1111][1111]...[1111]
- 以下同じ
つまりこれは、こういう事をやっているわけです。要するに総当り。
- [11]が整数個連続する文字列と完全一致するか否か = 2で割り切れるか否か
- [111]が整数個連続する文字列と完全一致するか否か = 3で割り切れるか否か
- [1111]が整数個連続する文字列と完全一致するか否か = 4で割り切れるか否か
- 以下同じ
しかも素数で順次割っているわけではなくて、例えば"2"と"4"で重複している(4で割り切れる→2で割り切れる)ので、
これ以上無いくらい効率の悪いルーチンになっています。そもそもこれ自体ネタだから別にいいんだけど。
全く同じことをやるJavascriptのコードは次の通り。まあいちいち書くのも馬鹿らしいですが。
function isPrime(/* int */ num) { return (function(/* int */ divider) { return (num <= divider) || ((num % divider != 0) && arguments.callee(divider + 1)); })(2); }
うーむ、もっとスマートな書き方はないものか。まあ素直にループを使えばいいんだけど、それじゃツマラン。
ちなみに、あまりデカイ値を喰わせるとスタックオーバーフローします。
末尾再帰の最適化ができれば話は別なんですが、現状そういう処理系はないっぽい。