原です。

2の倍数を取り除くのがどうももったいないと思っていたら、ちょ
うど「アルゴリズム事典」(奥村晴彦著、技術評論社)に

(奥村1)
max = Integer(ARGV.shift || 100)
max2 = (max-3)/2
primes = [2]
sieve = (0 .. max2).to_a
for i in 0 .. max2
  if sieve[i]
    k = i+i+3
    primes.push k
    (k+i).step(max2, k) do |j|
      sieve[j] = nil
    end
  end
end
puts primes.join(", ")

という感じのプログラムがあって若干(稲葉1)より速いみたいでした。
i+i+3 の計算にはあまりコストがかからないみたいです。そこで、両
方をミックスしてみました。

(原6)
max = Integer(ARGV.shift || 100)
max2 = (max-3)/2
primes = [2]
sieve = (0 .. max2).to_a
for i in 0 .. (Math.sqrt(max)-3)/2 
  next unless sieve[i]
  k = (i<<1)+3
  (k*(i+1)+i).step(max2, k) do |j|
    sieve[j] = nil
  end
end
primes.concat sieve.compact.collect { |i| (i<<1)+3 }
puts primes.join(", ")

するとある程度 max が大きいと(稲葉1)の大体3倍のスピード
が出るようです。