原です。

|  % はやはり遅い

うーん、かならずしもそうでもないみたいです。

(原5)
max = Integer(ARGV.shift || 100)
def primes(max)
  return [2] if max <= 2
  n = Integer(Math.sqrt(max))
  sieve = (n+1 .. max).to_a
  r = primes(n)
  r.each do |x|
    sieve = sieve.find_all{ |i| i % x != 0 }
  end
  r.concat sieve
end
puts primes(max).join ", "

これの結果が

-- sinara5 --
elapsed time: 0.062559 second
user time: 0.0666667 second
system time: 0.0 second

と、かなり速い。