From: WATANABE Hirofumi <eban@...>
Date: 1999-03-21T17:20:38+09:00
Subject: [ruby-list:13046] Re: Sieve of Eratosthenes (Re: [ruby-dev:6094])

わたなべです.

Shin-ichiro Hara <sinara@blade.nagaokaut.ac.jp> writes:

:(原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)の大体３倍のスピード
:が出るようです。

profile を取ってみると Float#< が結構上位にいるので
  for i in 0 .. (Math.sqrt(max)-3)/2
を
  for i in 0 .. Integer((Math.sqrt(max)-3)/2)
にするとちょっと速くなります(微々たるもんだけど).

-- 
わたなべひろふみ