自動ニュース作成G
正規表現で素数判定
http://d.hatena.ne.jp/ytakano/20100721/1279736214
2010-07-22 13:12:28
>/^1?$|^(11+?)\1+$/
>という正規表現を使うと,素数判定が出来るらしい.
黒魔術レベルの正規表現
・去年くらいに似たような事考えてたが証明できなくて放置してた...あれホントだったんだー。・>追記:ハッキリ言ってこの正規表現はネタなので,実際に素数判定を行いたい場合は,もっと別な賢いアルゴリズムを使ったほうが良いです・いつものアレ置いておきますね http://www.din.or.jp/~ohzaki/mail_regex.htm・あー、なるほど。最大の長さ以外で割れるかどうかを判断してるのな。滅茶苦茶重そうw・最大計算量なんぼ?・O(n)・総当りがこれだけ短く記述できるのは凄いのかもしれない・10億付近の数値を素数判定するのに10億バイト使うのか。。。このオチャメさんめ・効率が良いかどうかは別として10億バイトって1GBだから今なら動くPCも珍しくないね