無茶しやがって…(褒め言葉)

なんかすごいですコレ。素数判定する正規表現だとか。完全にネタですねこりゃ。

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

この正規表現に、素数判定したい数字の値ぶんだけ"1"を連結した文字列をマッチさせます。
つまり3が素数かどうかを判定したい場合、与える文字列は"111"です。

詳しくはコチラを参照。
http://d.hatena.ne.jp/ytakano/20100721/1279736214

どうなってんのこれ

この正規表現の構造を解析してみます。

まず

^1?$

の部分はいいですよね。1かどうかを判定しています。

で、問題のこの部分なわけですが。

^(11+?)\1+$

えーと、"1"が2個以上かつ最小マッチで、それと同じ正規表現が後ろに1個以上続く…ってか。
振る舞いをシミュレートしてみると次のような感じ。("[11...]"は(11+?)が喰う"1"の数を表します)

1. [11][11][11]...[11]
2. [111][111][111]...[111]
3. [1111][1111][1111]...[1111]
4. 以下同じ

つまりこれは、こういう事をやっているわけです。要するに総当り。

1. [11]が整数個連続する文字列と完全一致するか否か ＝ 2で割り切れるか否か
2. [111]が整数個連続する文字列と完全一致するか否か ＝ 3で割り切れるか否か
3. [1111]が整数個連続する文字列と完全一致するか否か ＝ 4で割り切れるか否か
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);
}

うーむ、もっとスマートな書き方はないものか。まあ素直にループを使えばいいんだけど、それじゃツマラン。

ちなみに、あまりデカイ値を喰わせるとスタックオーバーフローします。
末尾再帰の最適化ができれば話は別なんですが、現状そういう処理系はないっぽい。