[ruby-dev:6075] Re: sieve.rb

えぐち＠エスアンドイー です。

>>> In message [ruby-dev:6074] sieve.rb
    On Mon, 8 Mar 1999 01:08:04 +0900, WATANABE Hirofumi <[e-mail]> said:

eban> わたなべです.
eban> 
eban> Yukihiro Matsumoto <[e-mail]> writes:
eban> 
eban> :|前から気になっていたのですが、 sample/sieve.rb で使われている
eban> :|アルゴリズムは、「エラトステネスのふるい」ではないと思うのですが、
eban> :|どうでしょう？
eban> :
eban> :えー，そうなんですか？ そうだと信じてたのに..
eban> 
eban> たぶん最終的にやってることは同じだと思うけど,
eban> すなおに実装するとこんな感じですよね.
eban> ＃最適化はわざとしてない.
eban> 
eban> # sieve of Eratosthenes
eban> max = Integer(ARGV.shift || 100)
eban> sieve = []
eban> for i in 2 .. max
eban>   sieve << i
eban> end
eban> 
eban> for i in 2 .. max
eban>   sieve.delete_if do |d|
eban>     d != i and d % i == 0
eban>   end
eban> end
eban> print sieve.join(", "), "\n"

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

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

i = 2
while i * i <= max
  if sieve[i]
    j = i * i
    sieve[j] , j = false , j + i while j <= max
  end
  i += 1
end
a=[]
sieve.each_index{|d| a += d if sieve[d]}
puts a.join ', '

＃あんまり Ruby っぽくないですね ^^;;;;

eban> 1 は素数ではない.

おおせのとおり ^^;;

	えぐち