[ruby-list:12918] Sieve of Eratosthenes (Re: [ruby-dev:6094])

原です。

エラトステネスのふるい(素数のリストのアルゴリズム)について、
ruby-dev で話が出たのでここにまとめて紹介します。

最初に五十嵐さんが [ruby-dev:6060] で、現在の sample/sieve.rb
は「エラトステネスのふるい」ではないのではないか?という疑問が
出されました。sample/sieve.rb というのは、

(まつもと1)
sieve = []
if ! max = ARGV.shift; max = 100; end
max = max.to_i

for i in 2 .. max 
  begin
    for d in sieve
      fail if i % d == 0
    end
    print ", "
    print i
    sieve.push(i)
  rescue
  end
end
print "\n"

というものです。そこでわたなべさんが、

(わたなべ1 [ruby-dev:6074])
max = Integer(ARGV.shift || 100)
sieve = []
for i in 2 .. max
  sieve << i
end

for i in 2 .. max
  sieve.delete_if do |d|
    d != i and d % i == 0
  end
end
print sieve.join(", "), "\n"

というアルゴリズムを出して来たわけですが、えぐちさんが、
除剰算を使わないのがポイントではないかと次のアルゴリズム
を示しました。

(えぐち1 [ruby-dev:6075])
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 ', '

そこで更にわたなべさんが、最後に compact を使うだけに
配列生成を抑える次の方法をあげました。

(わたなべ2 [ruby-dev:6083])
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 ", "

さらに五十嵐さん自身の方法は以下の通り。

(五十嵐1[ruby-dev:6087])
limit = Integer(ARGV.shift || 100)
sieve = Array.new
primes = Array.new
sieve.fill(true, 2..limit)

2.upto(limit) do |i|
   if sieve[i]
      primes.push i
      (i*2).step(limit, i) do |j|
         sieve[j] = false
      end
   end
end

puts primes.join(",")

駄目押しの、稲葉さんによる(わたなべ2)の修正版が次です。

(稲葉1 [ruby-dev:6093])
max = Integer(ARGV.shift || 100)
sieve = []
for i in 2 .. max
  sieve[i] = i
end

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


で、私もこれがほぼ究極版だと思うのですが、いくつか付け加
えます。まず、(まつもと1)の修正版がこれ。

(原1)
max = Integer(ARGV.shift || 100)

primes = []
(2 .. max).each do |i|
  primes.push(i) unless primes.find{ |d| i % d == 0 }
end
puts primes.join ", "

プロセッサによるけど、これが一番早い可能性はあります。
次に % を使うけどかなり素直なふるいだと思われるのがこれ。
(わたなべ1)の修正版です。

(原2)
max = Integer(ARGV.shift || 100)
sieve = (2 .. max).to_a

k = 0
while i = sieve[k]
  sieve.delete_if{ |j|
    j > i && j % i == 0
  }
  k += 1
end
puts sieve.join ", "

これだと j > i という判定がもったいないのと、delete 自体のコ
ストが気になるけど、素数が「少ない」ことが前提となっています。
＃ほんとは max/log(max) ぐらいある。

そして最初に sieve を奇数だけにしたもの。

(原3)
max = Integer(ARGV.shift || 100)
sieve = [2] + (1 .. max/2).collect { |i| 2*i+1 }
k = 1
while i = sieve[k]
  sieve.delete_if{ |j|
    j > i && j % i == 0
  }
  k += 1
end
puts sieve.join ", "

＃こんなダイジェストを作ってしまう癖いつのまについたのかな。

ところで質問です。(原2)を

(原4)
max = Integer(ARGV.shift || 100)
sieve = (2 .. max).to_a

sieve.each { |i|
  sieve.delete_if{ |j|
    j > i && j % i == 0
  }
}
puts sieve.join ", "

と書いたら each は正常に動作するのは保証されてましたっけ?