正規表現で素数判定 - NO!と言えるようになりたい

追記：ハッキリ言ってこの正規表現はネタなので，実際に素数判定を行いたい場合は，もっと別な賢いアルゴリズムを使ったほうが良いです 正規表現で素数が判定できるという記事を見たので試してみた． 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で書いた素数判定プログラムはこん

[mygarage]

正規表現

[tyru]

今更分かった…そういうことだったのか… / id:Haaaa_N \N は再帰ではないです。再帰は (?N) ですね。 http://ngyuki.hatenablog.com/entry/2015/09/23/203737

[haya14busa]

なるほどおもしろい

[Haaaa_N]

後方参照って再帰できるんだなあ

[hazisarashi]

お〜記事にまとまってるのあった。

[Hash]

な、何が起こっているのか（ry

[kurumigi]

判定したい数の分だけ同じ文字を並べる→1でなく、かつ、他の数で割りきれるかを後方参照を用いてチェックする。

[slash_01]

へー。この発想はなかった。

[oooooooo]

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

[omine3]

こういうのを見てるとつくづく、あぁSQLと正規表現のプロになりたいなと思いますよね

[nakag0711]

最短一致の動作を復習

[mujin]

ただ単に2で割って、3で割って、4で割って…というループを正規表現にしてるだけ。魔法のタネが分かってしまうと、この程度のものだったのかとシンプルさに驚く。

[nasunori]

Ruby／

[goryugo]

正規表現で素数判定 - NO!と言えるようになりたい-

[Arison]

正規表現で素数判定。この考え方はすごい。

[ofsilvers]

面白い

[mrgoofy33]

あとで読む。 正規表現で素数判定 - NO!と言えるようになりたい

[NAT]

面白い。最短一致の +? がミソなのね。何度も繰り返し読んで、やっと理解。それにしても、これを考えた人はどうやってこれを思いついたのやら。

[simpleplay]

ああ、こういう方法があるんだ。効率は悪いけど、短くてきれい。わざわざ(11+?)としてある部分に美意識を感じる。

[teni-totte]

ああ、こういう方法があるんだ。効率は悪いけど、短くてきれい。わざわざ(11+?)としてある部分に美意識を感じる。

[TaKUMA]

おもしろいな

[adsty]

じっくり読み解けば仕組みが分かる。丁寧な解説のおかげ。

[rgssws4m]

エラトステネスの篩の正規表現実装。コードが短くてカッコイイけど実用ならミラー・ラビン法とかを使うのがよさそう。

[wacky]

nが素数かどうか正規表現で判定。「1」をn個並べて、/^1?$|^(11+?)\1+$/ にマッチしなければnは素数。発想が面白い。効率は無視。

[dgdg]

ああ…なるほど。理解するのにかなり時間がかかったorz /rubyを1年ぶりくらいに使った。忘れすぎ…

[Tensor]

あとで試す。

[AYNIK]

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

[Rewish]

ほっほー

[yocchi24]

これはすごい。面白い！

[overleo]

プログラムは美しいなあ。