どうも言葉が足りなかったようで、分かりにくくてすみません。
>>376で仰ってる通りの感じです。

Rubyなんで読みにくいかも知れませんが、一応そのあたりのことが
http://idm.s9.xrea.com/factorization/eratosthenes.html
に書いてあります。

# この文も直さなきゃなー。
# 「3,5,7の倍数を除いても無駄」とか書いてあるし。
# 昔、試したところでは確かにあまり効果が上がらなかったんだけれど、
# このスレ見てる限りではどうも私の実装が腐ってただけみたい。