From: wakou@...
Date: 1999-09-09T07:30:38+09:00
Subject: [ruby-list:16645] Re: Sieve of Eratosthenes (Re: [ruby-dev:6094])

青山です。

On Thu, 18 Mar 1999 17:21:54 +0900,
Shin-ichiro Hara <sinara@blade.nagaokaut.ac.jp> wrote:

> するとある程度 max が大きいと(稲葉1)の大体３倍のスピード
> が出るようです。

ちょっと古い話しですが、NIFTY の方でこの話が出まして、少し手を加えた所、
max が大きい場合、さらに倍ぐらいになりました。これでほぼ awk, perl の
速度に追い付いたようです。


max = Integer(ARGV.shift || 1000)                                               
max2 = (max-3)/2                                                                
sieve = Array.new(max2, true)                                                   
for i in 0 .. Integer((Math.sqrt(max)-3)/2)                                     
  next unless sieve[i]                                                          
  k = i+i+3                                                                     
  j = k*(i+1)+i                                                                 
  while j <= max2                                                               
    sieve[j] = nil                                                              
    j += k                                                                      
  end                                                                           
end                                                                             
for i in 0 .. max2                                                              
  sieve[i] && sieve[i]=i+i+3                                                    
end                                                                             
sieve.compact!                                                                  
puts 2, sieve.join("\n")                                                        


step --> while, compact --> compact!, Array.new の max とデフォルトの
利用、こんな感じで高速化しました。


-- 
青山 和光 Wakou Aoyama <wakou@fsinet.or.jp>