わたなべです.

EGUCHI Osamu <eguchi / shizuokanet.ne.jp> writes:

:素数の集合から消去すると言う点で、篩のアルゴリズムだと思いますが、
:オリジナルは除剰算を行なわない事が、肝だったように思います。
:＃最適化ってこれの事ですか？ ^^)l

だいたいそうです. 考えかたもえぐちさんのとほぼ同じです.
delete はコストが高いってのもありますね.

# sieve of Eratosthenes
max = Integer(ARGV.shift || 100)
sieve = []
for i in 2 .. max
  sieve[i] = i
end

for i in 2 .. Math.sqrt(max)
  (i+i).step(max, i) do |j|
    sieve[j] = nil
  end
end
puts sieve.compact.join ", "

true ではなく値そのもの, false ではなく nil を使うのがミソ.
compact が使えます.

-- 
わたなべひろふみ