読者です 読者をやめる 読者になる 読者になる

正規表現で素数探索

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とかをうまく使えば多少高速化の余地はあるかもしれない。