正規表現で素数探索

def sieve_regex(max)
  table = ' ' + (2..max).map{|i|i.to_s}.join(' ')
  (2..Math.sqrt(max)).each do |i|
    1 while table.gsub!(/^((?:\d* ){#{i-1}}(?:(?:\d* ){#{i}})+)\d+/){$1}
  end
  table
end

perl -le '$,=" "; print grep { (1 x $_) !~ /^(11+)\1+$/ } (2..100)' の方向でもうちょっとひねってみた。一応篩ではあるのだけれど、エラトステネスの篩と違って毎回テーブルの最初から探索しているので性能は推して知るべし。tableがそのまま素数のリストになっているあたりはちょっと新しいかもかも。\Gとかをうまく使えば多少高速化の余地はあるかもしれない。