最近のキーワード

2006年06月17日

正規表現マッチングによる素数判定

「perl - 100までの素数」や、そこから辿れる TPJ One Linersの「#6 Primality」を見てなるほどと思った。
perl -le 'print "PRIME" if (1 x shift) !~ /^(11+)\1+$/' 19
これで素数判定ができる。実際には、"1"でなくても構わない。(もちろん、"\1"は"\1"でないとダメだが…。) 数字を文字列長と見なして、素数であることの判定を、その文字列が、その部分文字列の結合だけから構成できないことを判定する問題に置き換えている。
さて、0から100までの数字から素数を集めてくるのを、この正規表現を使って解くと、Rubyならこうなるだろう。
p (2..100).select{|n| "1" * n !~ /^(11+)\1+$/ }
しかし、これでは、単純にすべての数字に対して、その数字に対応する文字列を作り、さらに、毎回正規表現マッチを行うので、奇抜なアイデアではあるが遅い。
posted by ttate at 13:27| ☔| Comment(0) | TrackBack(0) | プログラム言語 | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。

この記事へのトラックバック
×

この広告は180日以上新しい記事の投稿がないブログに表示されております。